帮忙分析下这个算法的时间
问题描述：考虑一个任意的整数序列。在这个序列的两个数之间可以插入运算符“+”或者“-”，这样得到不同的算术表达式，经过运算，每个表达式得到一个结果。让我们考虑下面的一个例子：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 次，将无法通过测试用例。
#include <stdio.h>
#define abs(x) ((x)>0?(x):(-(x)))
int main()
{
int yes=0,tmp,i,n,sum=0,p,s={0},in,stack;
scanf("%d %d",&n,&p);
for(i=0;i<n;i++)scanf("%d",&in);
for(i=0;i<n;i++)
{
tmp=abs(in)%p;
s++;
}
stack=-1;
for(i=1;i<p;i++)stack=1;
i=1;
while(1)
{
sum+=s*(stack?i:(p-i));
i++;
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;
}
}
if(yes){printf("Divisible");}else printf("Not divisible");
return 0;
}
最坏情况不是2^99吗？
[ 本帖最后由 iptton 于 2006-6-10 01:45 编辑 ] 当输入为１００个数时 都世界杯去了。。。 sum+=s*(stack?i:(p-i));
这里是不是每次把所有余i的要么全部加要么全部减?
如果s=3,那么是不是余2的3个数要么全加,要么全减?
有加有减的情况呢? 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;
}
这段是一个回溯算法，实现了这个功能 原帖由 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）。 我的算法不是简单的对输入进行遍历……
而是对输入进行取余……还有补码方面的知识……
应该是那个while执行得太频繁……
但时间一定不是2^9999
我的方法
将题目规定的运算解析为求模运算（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，hit=1时表示L mod k 可以等于i， 也即i属于S。
算法：
（1）顺序扫描L，对于每个元素l跟hit得为1得元素的序号i（hit=1），进行“和后求模” 和“差后求模”运算，各自所得结果为j1和j2，更新hit=1， hit=1。如果hit=1，则L mod k 可以等于0， 也就是L 可以被k整除。就可以结束扫描了。
（2）扫描过程中没有修改hit＝1，也就是L不能被k整除。
复杂度为O（N×k），如果用穷举法则要2^N，其实是编历高度为N的二叉树的所有叶子。 楼上的可以写下整个程序吗？
有点看不明白……
我那个是2^99再优化也是2^45都是太大了。。。
这道题在北大的ＡＣＭＯＮＬＩＮＥJUDGE上有 题号是 1745
另一个算法：
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
int fun(int a,int k)/* 转换为在K的一半以内的数 */
{
int i;
i=abs(a%k);
i=i>(k/2)?(k-i):i;
return i;
}
int *nu(int *a,int b,int k)/* 实现加减 */
{
int *c,i,j;
j=k/2+1;
c=(int *)malloc(j*sizeof(int));
memset(c,0,j*sizeof(int));
for(i=0;i<j;i++)
{
if(!a)continue;
else {c=1;c=1;}
}
return c;
}
int main()
{
int *a,n,k,i,b;
/*scanf("%d%d",&n,&k);*/
randomize();
n=100;k=rand()%100;
i=k/2+1;
a=(int *)malloc(i*sizeof(int));
memset(a,0,i*sizeof(int));
a=1;
for(i=0;i<n;i++)
{
/*scanf("%d",&b);*/
b=rand()%10000;
if(b%k==0)continue;
else a=nu(a,b,k);
}
if(a==1)printf("Divisible");
else printf("Not divisible");
getch();
return 0;
}
页:
[1]