Problem solving with programming: Jolly jumpers problem

Problem solving with programming: Jolly jumpers problem

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3  

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly ? why 3 3 2 1, two 3
Not jolly

Compute diff and make a decision at same time. Traverse once only.

while( !(cin >> n).eof() )


{




int i;




for( i = 0; i < n ; i++ )


{


cin >> array[i]; 


}




for( i = 1; i < n; i++ )


diff[i] = 0;




for( i = 0; i < n-1; i++ )


{


int d = abs( array[i]-array[i+1] );


if( d < 1 || d > n-1 || diff[d] == 1 )


{


cout << "Not jolly" << endl;


break;


}


diff[d] = 1;


}




if( i == n-1 )


{


cout << "Jolly" <<endl;


}


}

DIff array, then sort or use priority queue.
https://saicheems.wordpress.com/2013/08/16/uva-10038-jolly-jumpers/
http://acmproblemsolution.blogspot.com/2013/01/solution-of-10038-jolly-jumpers.html

https://segmentfault.com/a/1190000006680690

仔細思考可得以下幾點:

1. 若兩數差值為k, k > length(array)-1則 not jolly (根據上述只記錄1~n-1的值所以不能大於n-1)
2. 記錄完所有兩數差值之後,檢查1~n-1的值皆存在則為jolly

bool check(int *nums,bool *record,int length){
    
    for(int i = 1 ; i < length ; i++){
        int temp = abs(nums[i] - nums[i-1]);
        if(temp > length - 1)
            return false;
        record[temp] = true;
    }
    
    for(int i = 1 ; i < length ; i++){
        if(!record[i])
            return false;
    }
    return true;

}

int main(){
    int length;
    while(cin >> length){
        int nums[3001] = {0};
        bool record[3001]= {false};
        
        for(int i = 0 ; i < length ; i++){
            cin >> nums[i];
        }
        
        if(check(nums,record,length))
            cout << "Jolly" << endl;
        else
            cout << "Not jolly" << endl;
        
    }
 }

另一種解法一樣是使用表格記錄,只是用了不同的判斷方式:

1. 在記錄兩數差值k的時候,順便去看表格,如果k本來已經存在,則為not jolly (因為有n個數)
2. 若兩數的差值k, k = 0 或 k > length - 1 則 not jolly.
3. 若不為not jolly,則為 jolly

bool check(int *nums,bool *record,int length){
    
    for(int i = 1 ; i < length ; i++){
        int temp = abs(nums[i] - nums[i-1]);
        if(temp > length - 1 || temp == 0 || record[temp])
            return false;
        record[temp] = true;
    }
    return true;
}

Read full article from Problem solving with programming: Jolly jumpers problem