【UVa】10038 - Jolly Jumpers

英文題目傳送門，中文題目傳送門

如果一串數列有n個元素，其兩兩相減產生的絕對值，可以事後由小而大排序成1~n-1的話，便稱為Jolly Jumper數列。

所以根據題目附上的範例

inputArray_1[] = 1 4 2 3

abs_of_difference[] = 3 2 1

==>Jolly

inputArray_2[] = 1 4 2 -1 6

abs_of_difference[] = 3 2 3 7

==> Not Jolly

另外要注意的是，差值的絕對值並不需要有特別的大小依序關係，只要算出來的所有的絕對值都是1~n-1範圍內唯一一個數值就可以了。

數列1 2 4為Jolly，差值的絕對值為1 2（符合1~n-1 [ = 2] 的條件）

數列1 3 4也為Jolly，差值的絕對值為2 1（符合1~n-1 [ = 2] 的條件）

解題的過程可以分成下面三個步驟

1. 取得第一位代表共有幾位數字的數值，賦予變數inputCount
2. 以步驟一取得的數值做為for迴圈的邊界數值，將後續數值陣列賦予inputArray
3. #include <math.h>使用abs()，使用for迴圈輪巡過一次inputArray陣列，算出兩兩數值間差值的絕對值，這邊宣告了另一個陣列jollyArray，用來儲存已出現數值的tag，例如當絕對值算出來為3，則jollyArray[3] = 1，表示數值3已經出現過了
4. 最後使用for迴圈輪巡jollyArray，如果發現有元素數值為0，表示該差值沒有被計算出來，不滿足題目的條件，將isJolly = 0，由isJolly來判斷並印出訊息

程式碼如下：

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int main(int argc , char *argv []){

       

    int i, inputCount = 1; 

    int inputArray[3000] = {0};

       

    while(scanf("%d", &inputCount) != EOF){

        if (inputCount == 0)

             break;

       

        for (i = 0; i < inputCount; i++){

            scanf("%d", &inputArray[i]);

         }

        

         /*

        printf("input integers:");

        for (i = 0; i < inputCount; i++){

            printf("%d ", inputArray[i]);

        }

        printf("\n");

        */

                    

         int jollyArray[3000] = {0};

        

         for (i = 1; i < inputCount; i++){

            jollyArray[abs(inputArray [i] - inputArray[i - 1])] = 1;

         }

                

         /*

        for (i = 1; i < inputCount; i++){

            printf("jollyArray[%d] = %d\n", i, jollyArray[i]);

        }

        printf("\n");

        */

        

         int isJolly = 1;

        

         for (i = 1; i < inputCount; i++){

             if (jollyArray[i] != 1){

                isJolly = 0;

                 break;

             }

         }

        

         if (isJolly == 1)

            printf("Jolly\n");

         else

            printf("Not jolly\n");

            

    }

    return 0;

}

這題主要練習的部分應該是最後的那個步驟，透過更改特定元素的數值來進行標示的手法，如果是初次看見的童鞋可能需要一點時間消化記憶一下。

這封郵件來自 Evernote。Evernote 是您專屬的工作空間，免費下載 Evernote