帮忙分析下这个算法的时间

iptton

问题描述：

考虑一个任意的整数序列。在这个序列的两个数之间可以插入运算符“+”或者“-”，这样得到不同的算术表达式，经过运算，每个表达式得到一个结果。让我们考虑下面的一个例子：17, 5, -21, 15。这个序列有8个可能的算术表达式：



17 + 5 + (-21) + 15 = 1617 + 5 + (-21) - 15 = -1417 + 5 - (-21) + 15 = 5817 + 5 - (-21) - 15 = 2817 - 5 + (-21) + 15 = 617 - 5 + (-21) - 15 = 2417 - 5 - (-21) + 15 = 4817 - 5 - (-21) - 15 = 18如果上述八个表达式中的某个能被 k 整除，那么我们成这个整数序列能被 k 整除。在上例中，序列能被 7 整除 (17+5+(-21)-15=-14)，但却不能被 5 整除。



要求你写出一个程序来测试输入序列能否被 k 整除。



输入


输入第一行包括两个整数 N 和 k，其中 1 <= N <= 10000，2 <= k <= 100，他们之间以空格分开。



第二行是由N个整数组成的序列，整数与整数之间用空格分开，每个整数的绝对值不超过10000。



输出


如果序列能被 k 整除，那么输出 Yes，否则输出 No。



提示


此题目若使用穷举的方法，最坏情况下需计算 29999 次，将无法通过测试用例。

1. 
   
2. #include <stdio.h>
   
3. #define abs(x) ((x)>0?(x):(-(x)))
   
4. int main()
   
5. {
   
6.   int yes=0,tmp,i,n,sum=0,p,s[100]={0},in[10000],stack[100];
   
7.   scanf("%d %d",&n,&p);
   
8.   for(i=0;i<n;i++)scanf("%d",&in[i]);
   
9.   for(i=0;i<n;i++)
   
10.   {
    
11.     tmp=abs(in[i])%p;
    
12.     s[tmp]++;
    
13.   }
    
14.   stack[0]=-1;
    
15.   for(i=1;i<p;i++)stack[i]=1;
    
16.   i=1;
    
17.   while(1)
    
18.   {
    
19.     sum+=s[i]*(stack[i]?i:(p-i));
    
20.     i++;
    
21.     if(i==p)
    
22.     {
    
23.       i--;
    
24.       if(sum%p==0){yes=1;break;}
    
25.       while(stack[i]==0)i--;
    
26.       if(i==0)break;
    
27.       stack[i]=0;
    
28.       for(i+=1;i<p;i++)stack[i]=1;
    
29.       i=1;sum=0;
    
30.      }
    
31.    }
    
32.   if(yes){printf("Divisible");}else printf("Not divisible");
    
33.   return 0;
    
34. }

复制代码

最坏情况不是  2^99  吗？

[ 本帖最后由 iptton 于 2006-6-10 01:45 编辑 ]

iptton

当输入为  １００个数时

iptton

都世界杯去了。。。

麦当劳叔叔

sum+=s*(stack?i:(p-i));
这里是不是每次把所有余i的要么全部加要么全部减?
如果s[2]=3,那么是不是余2的3个数要么全加,要么全减?
有加有减的情况呢?

iptton

if(i==p)
    {
      i--;
      if(sum%p==0){yes=1;break;}
      while(stack==0)i--;
      if(i==0)break;
      stack=0;
      for(i+=1;i<p;i++)stack=1;
      i=1;sum=0;
     }
这段是一个回溯算法，实现了这个功能

我不知道WHY

原帖由 iptton 于 2006-6-9 22:06 发表
此题目若使用穷举的方法，最坏情况下需计算 29999 次，将无法通过测试用例。

这句话的意思是此题目若使用穷举的方法，时间复杂度T(n)=2^9999，将无法通过测试用例。

原帖由 iptton 于 2006-6-9 22:06 发表
最坏情况不是  2^99  吗？

So最坏情况不是2^99，而是2^9999。

分析：
1,由N个整数组成的序列，会得到2^(N-1)不同的算术表达式。
2,每个表达式要做N次运算。
3,max(N)＝10000。
所以若使用穷举的方法，最坏情况下需计算 10000*2^9999次。
T（10000*2^9999）＝0（2^9999）。

iptton

我的算法不是简单的对输入进行遍历  ……

而是对输入进行取余……  还有补码方面的知识……  

应该是那个while执行得太频繁……

但时间一定不是2^9999

yonhe

将题目规定的运算解析为求模运算（mod），问题就转为： 数列L mod k 是否可以等于0。

设S为 L mod k 的所有数的集合，这样表示吧：S ＝ F（ L ）。

假设subL是L的子集，subS＝F（subL），那么subS与S有什么关系呢？可以推出subS是S的子集。而且利用subS和 L－subL （集合的差运算）也可以求出S来。

基于这个原理，可以用递推的方法求得S，设置hit[0...k]，hit=1时表示L mod k 可以等于i， 也即i属于S。

算法：
（1）顺序扫描L，对于每个元素l跟hit得为1得元素的序号i（hit=1），进行“和后求模” 和“差后求模”运算，各自所得结果为j1和j2，更新hit[j1]=1， hit[j2]=1。如果hit[0]=1，则L mod k 可以等于0， 也就是L 可以被k整除。就可以结束扫描了。
（2）扫描过程中没有修改hit[0]＝1，也就是L不能被k整除。

复杂度为O（N×k），如果用穷举法则要2^N，其实是编历高度为N的二叉树的所有叶子。

iptton

楼上的可以写下整个程序吗？

有点看不明白……

我那个是2^99再优化也是2^45都是太大了。。。

这道题在北大的ＡＣＭ  ＯＮＬＩＮＥ  JUDGE  上有 题号是 1745

另一个算法：

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. #include <string.h>
   
5. #include <stdlib.h>
   
6. int fun(int a,int k)/* 转换为在K的一半以内的数 */
   
7. {
   
8.     int i;
   
9.     i=abs(a%k);
   
10.     i=i>(k/2)?(k-i):i;
    
11.     return i;
    
12. }
    
13. int *nu(int *a,int b,int k)/* 实现加减 */
    
14. {
    
15.     int *c,i,j;   
    
16.     j=k/2+1;
    
17.     c=(int *)malloc(j*sizeof(int));
    
18.     memset(c,0,j*sizeof(int));
    
19.     for(i=0;i<j;i++)
    
20.     {
    
21.         if(!a[i])continue;
    
22.         else {c[fun((i+b),k)]=1;c[fun((i-b),k)]=1;}
    
23.     }
    
24.     return c;
    
25. }
    
26. int main()
    
27. {
    
28.     int *a,n,k,i,b;
    
29.     /*scanf("%d%d",&n,&k);*/
    
30.     randomize();
    
31.     n=100;k=rand()%100;
    
32.     i=k/2+1;
    
33.     a=(int *)malloc(i*sizeof(int));
    
34.     memset(a,0,i*sizeof(int));
    
35.     a[0]=1;   
    
36.     for(i=0;i<n;i++)
    
37.     {
    
38.         /*scanf("%d",&b);*/
    
39.         b=rand()%10000;
    
40.         if(b%k==0)continue;
    
41.         else a=nu(a,b,k);   
    
42.     }   
    
43.     if(a[0]==1)printf("Divisible");
    
44.     else printf("Not divisible");
    
45.     getch();
    
46.     return 0;
    
47. }
    

复制代码