Problem 326 Extrapolation Using a Difference Table，用差分表算外差

這題的差分表並不是真的要你宣告一個很大的陣列來儲存差分表，根據他最後的提示，似乎會給你一個很大的 k 值，如果你將每個值都存起來，可能就會有記憶體消耗的問題。
我的作法是先將每一行的最後一個值算出來，存在一個全域變數的陣列中，並使用遞迴呼叫來做解算。因為題目說最多只有10個值，所以遞迴所用的陣列大小10個就夠用。在下面的例子中，lastValue和m_index都是全域變數，每呼叫一次，就計算一行的差分值，然後只要將最後的一個值存起來，放入lastValue中就OK了。

void compDiff(int eArray[], int size)
{
    int ary[10]={0}, i;
    if (size==2)
    {
        m_index++;
        lastValue[m_index] = eArray[1]-eArray[0];
    }
    else
    {
        for (i=1;i<size;i++)
            ary[i-1] = eArray[i]-eArray[i-1];
        m_index++;
        lastValue[m_index] = ary[i-2];
        compDiff(ary,size-1);
    }
}

每一行最後的值算完後，再重複k次，每次再更新lastValue的每個值，使用
lastValue[j] += lastValue[j+1];
這樣就大功告成了。
p326題目連結
回ACM題庫目錄
回首頁

Problem 263 Number Chains，數字鏈

這個題目適合剛學C語言的人來練習，其中數字轉變成最大或最小值的方法，只要用簡單的Bubble Sort就可以了。這題的挑戰點在如何判斷輸入的數字是幾位數，當將輸入值拆成一個一個的個數後，最後面一定會有剩下 0 的情形，所以將陣列大小減去最後剩下多少零，就可以判斷位數了。參考下列程式片斷，如果digit[i]!=0，則位數i+1就出來了。

    i = 9;
    while (i>=0)
    {
        if (digit[i]!=0)
        {
            size = i+1;
            break;
        }
        i--;
    }

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

C 程式設計期末作業，解題練習：解答

/* C Programming, final project */
#include <stdio.h>
#include <stdlib.h>

int getSortedNum(int, int);
int numInChain(int, int);
int chain[1000];
int main(void)
{
    int num, size, idx;
    int bigNum, smallNum;
    while (1)
    {
        scanf("%d", &num);
        if (num==0)
            break;
        printf("Original number was %d\n", num);
        idx = 0;
        do
        {
            bigNum = getSortedNum(num,1);
            smallNum = getSortedNum(num,-1);
            chain[idx] = bigNum - smallNum;
            num = chain[idx];
            printf("%d - %d = %d\n", bigNum, smallNum, chain[idx]);
            idx++;
        } while (!numInChain(chain[idx-1], idx-2));
        printf("Chain length %d\n\n",idx);
    }

    return 0;
}

int getSortedNum(int num, int order)
{
    int digit[10]={0};
    int i, j, temp, size=0;
    
    for (i=0; i<10; i++)
    {
        digit[i] = num%10;
        num /= 10;
    }
    i = 9;
    while (i>=0)
    {
        if (digit[i]!=0)
        {
            size = i+1;
            break;
        }
        i--;
    }
    if (order == 1)
    {
        for (i=0;i<size-1;i++)
            for (j=i; j<size; j++)
                if (digit[i]<digit[j])
                {
                    temp = digit[i];
                    digit[i] = digit[j];
                    digit[j] = temp;
                }
    }
    else if (order == -1)
    {
        for (i=0;i<size-1;i++)
            for (j=i; j<size; j++)
                if (digit[i]>digit[j])
                {
                    temp = digit[i];
                    digit[i] = digit[j];
                    digit[j] = temp;
                }
    }
    temp = digit[0];
    for (i=1;i<size;i++)
    {
        temp *= 10;
        temp += digit[i];
    }
    return temp;
}

int numInChain(int newNum, int idx)
{
    int i;
    for (i=0;i<=idx;i++)
        if (newNum == chain[i])
            return 1;
    return 0;
}

作業五題目
回到首頁

期末考(D)題目：解答

#include <stdio.h>
#include <stdlib.h>

void print_tri(int);
int main(void)
{
    int n;
    printf("Enter a positive number: ");
    scanf("%d", &n);
    print_tri(n);
    
    system("pause");
    return 0;
}

void print_tri(int n)
{
    int i,j;
    for (i=0;i<=n;i++)
    {
        for (j=0;j<i;j++)
            printf(" ");
        for (j=2*n+1;j>2*i;j--)
        {
            printf("%d", j);
        }
        printf("\n");
    }
}

期末考(D)題目
返回小考目錄
回到首頁

期末考(D)題目

/* C Programming, final exam D */
/*
期末考題目：完成一個 print_tri 函數，以列印排列的數字，
            若輸入值為 n ，則第一列印出2n+1到 1 的數，
            第二列印出2n+1到 3 的數，依此類推，最後
            一列只印出2n+1，列印時以等腰倒三角形形式
            印出。例如輸入 4 時，輸出
            
            987654321
             9876543
              98765
               987
                9 

            輸入 1 時，輸出
            
            321
             3
                
函數輸入值：一個 int。 
函數輸出值： 無。 
題目輸入：一個大於等於 0 的整數 
題目輸出：印出等腰倒三角形。 
*/

解答下載
返回小考目錄
回到首頁

期末考(C)題目：解答

#include <stdio.h>
#include <stdlib.h>

void print_tri(int);
int main(void)
{
    int n;
    printf("Enter a positive number: ");
    scanf("%d", &n);
    print_tri(n);
    
    system("pause");
    return 0;
}

void print_tri(int n)
{
    int i,j;
    for (i=0;i<n;i++)
    {
        for (j=0;j<i;j++)
            printf(" ");
        for (j=n;j>i;j--)
        {
            printf("%d", j);
        }
        printf("\n");
    }
}

期末考(C)題目
返回小考目錄
回到首頁

期末考(C)題目

/* C Programming, final exam A */
/*
期末考題目：完成一個 print_tri 函數，以列印排列的數字。例如輸入 6 
            時，輸出
              654321
             65432
              6543
               654
                65
                 6 

            輸入 4 時，輸出
              4321
             432
              43
               4
                
函數輸入值：一個 int。 
函數輸出值： 無。 
題目輸入：一個整數 
題目輸出：印出倒三角形。 
*/

解答下載
返回小考目錄
回到首頁