Problem 146 ID Codes，識別碼

此題需要將輸入字串依照字串排序，印出它下一次會出現的字串排序。

舉個例子，對於abc字串的排序一共有六種，分別是：
abc
acb
bac
bca
cab
cba
當我輸入 cab 時，需要輸出 cba，也就是它下一次會出現的字串排序，可當我輸入 cba 時，因為它已是排序結尾，所以要輸出 No Successor。

對於這一題 C++ 可以使用 Algorithm 的 next_permutation() 方能輕易解出，可我們網站標榜「C的解題」，總不能掛羊頭賣狗肉吧！所以我又上網找了一些關於這題的演算法，因此寫出以下函式：

#define MAXLEN 60

char str[MAXLEN];

void swap(int i, int j)
{
     char tmp;
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
} 

int next_permutation()
{
    int i, j, k;
    int length;
    length = strlen(str);
    for(i = length - 1;i > 0 ; --i)
        if(str[i-1] < str[i]) break;
    j = i;
    if(j == 0) return 0;
    for(i = length - 1;i > 0; --i)
        if(str[j-1] < str[i]) break;
    k = i;
    swap(j-1, k);
    for(i = j, j = length - 1;i < j; ++i, --j)
        swap(i, j);
    return 1;
}

以上程式碼參考來源

以上函式可以方便找到下一次出現的字串排序，再接著只需判斷它是否有下一次的字串，將它印出即可。
By David.K

p146題目連結
回ACM題庫目錄
回首頁

Problem 424 Integer Inquiry，大數加法

這題就是簡單的大數加法，只要會大數加法，很輕易就寫出來了。

先創建一個結構(struct)，AN1 和 AN2，AN1為累加結果，AN2讀入每次輸入的大數並與AN1相加：

#define NUMLEN 200

struct AddNum
{
    int num[NUMLEN];
    int length;
};

struct AddNum AN1, AN2;
char numStr[101];

再讀入字串並反轉為整數陣列(integer array)：

gets(numStr);
if (numStr[0] == '0') break;
AN2.length = strlen(numStr) - 1;
for (i = AN2.length, j = 0; i >= 0; i --, j ++)
    AN2.num[j] = numStr[i] - '0'; 
for (i = 0; i < NUMLEN; i ++)
{
    AN1.num[i] += AN2.num[i];
    if (AN1.num[i] >= 10)
       AN1.num[i + 1] ++, AN1.num[i] %= 10;
}

最後AN1和AN2相加：

for (i = 0; i < NUMLEN; i ++)
{
    AN1.num[i] += AN2.num[i];
    if (AN1.num[i] >= 10)
       AN1.num[i + 1] ++, AN1.num[i] %= 10;
}

再將結果印出就可以了。
By David.K

p424題目連結
回ACM題庫目錄
回首頁

Problem 495 Fibonacci Freeze，大數費氏級數

此題為大數題，只需用到大數中的加法就可以了。

還是不例外，創建一個結構(struct)來使用：

#define LEN 5001
#define NUMLEN 1050

struct FibNum
{
    int num[NUMLEN];
    int length;
};

struct FibNum FN[LEN];

將第0個索引的num設定為0，第1個索引的num設定為1：

FN[0].num[0] = 0, FN[0].length = 0, 
FN[1].num[0] = 1, FN[1].length = 0;

接著利用Fib(0) = 0、Fib(1) = 1，當n > 2，Fib(n) = Fib(n-1) + Fib(n-2)的觀念，用大數加法算出到5000之內的Fib值，順便紀錄長度：

int i, j, k, n;

for (i = 2; i < LEN; i ++)
{
     for (j = 0; j < NUMLEN; j ++)
     {
         FN[i].num[j] += FN[i - 1].num[j] + FN[i - 2].num[j];
         if (FN[i].num[j] >= 10)
            FN[i].num[j + 1] ++, FN[i].num[j] %= 10;
     }
     for (j = NUMLEN - 1; ; j--)
         if (FN[i].num[j] > 0)
            break;
     FN[i].length = j ;       
}

最後，只須對應輸入值將大數取出就行了：

while (1)
{
     if (scanf("%d", &n) < 1) break;
     printf("The Fibonacci number for %d is ", n);
     for (i = FN[n].length ;i >= 0 ; i--)
          printf("%d", FN[n].num[i]);
     printf("\n");
}

不過成效不太好，用了0.368秒，我相信會有更好的方法。
By David.K

p495題目連結
回ACM題庫目錄
回首頁