Ducci序列 (Ducci Sequence)(模拟)

左手的ㄟ右手 2022-11-30 04:15 140阅读 0赞

对于一个n元组（a1,a2,…,an），可以对每个数求出它和下一个数的差的绝对值，得到一个新的n元组(|a1-a2|,|a2-a3|,…,|an-a1|)。重复这个过程，得到的序列成为Ducci序列，例如： (8,11,2,7)->(3,9,5,1)->(6,4,4,2)->(2,0,2,4)->(2,2,2,2)->(0,0,0,0). 也有的Ducci序列最终会循环。输入n元组（3≤n≤15），你的任务是判断它最终会变成0还是会循环。输入保证最多1000步就会变成0或循环。  
输入格式： 第一行是一个整数T，表示有T组数据。 每组数据第一行是一个整数n（3≤n≤15），表示Ducci序列的长度。第二行有n个树Ai（0≤Ai≤1000）. 输出格式： 如果最终会循环，输出LOOP，否则输出ZERO.  
样例输入：

4
    4
    8 11 2 7
    5
    4 2 0 2 0
    7
    0 0 0 0 0 0 0
    6
    1 2 3 1 2 3

样例输出：

ZERO
    LOOP
    ZERO
    LOOP

//题目保证最多1000步就会变成0或循环，对于不太大的数据可以直接使用模拟
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int a[16],temp[16],n,t,tot;
    bool flag;
    void ope()
    { 
        for(int i=1;i<=n;i++)
        { 
      	if(i!=n)
      	{ 
                temp[i]=abs(a[i]-a[i+1]);
            }
            else
            { 
                temp[i]=abs(a[i]-a[1]);
            }
        }
        for(int i=1;i<=n;i++)
        { 
      	a[i]=temp[i];
        }
    } 
    int main()
    { 
        cin>>t;
        while(t--)
        { 
      	cin>>n;
      	for(int i=1;i<=n;i++)
      	{ 
                cin>>a[i];
            }
            tot=100;
      	while(tot--)
      	{ 
                ope();
                flag=true;
                for(int i=1;i<=n;i++)//不必判断是否循环，直接操作100次，只要没变成0，就是循环。
                { 
        		if(a[i]!=0)
        		{ 
                        flag=false;
        		}
                }
       	    if(flag)
                { 
        		printf("ZERO\n");
        		break;
                }
      	}
      	if(!flag)
     	{ 
                printf("LOOP\n");
      	}
        }
        return 0;
    }