sdnd2000 发表于 2008-4-12 04:12

麻烦大家看看这个题目

从A这个序列中要求找到一对和为90的数。该用什么算法，麻烦大家具体说说   
A=（2，10，12，20，25，30，50，60，70，85，90，100，120，150，200）
谢谢大家。

张信哲 发表于 2008-4-12 17:11

啊是顺序表啊，感觉数组

张信哲 发表于 2008-4-12 17:22

#include<stdio.h>
void main()
{
        int a[]={2,10,12,20,25,30,50,60,70,85,90,100,120,150,200};
        int i,j;
        for(i=0;i<15;i++)
        {
                for(j=i+1;j<15;j++)
                        if(a[i]+a[j]==90)
                                printf("a[i]+a[j]=90 is %d+%d=90",a[i],a[j]);
        }
}

卧龙孔明 发表于 2008-4-12 18:27

DP
背包问题

wuxueyan2008 发表于 2008-4-12 21:11

还是诸葛孔明厉害，一言击中，就是背包问题！！数学建模上有！！

sdnd2000 发表于 2008-4-12 21:15

谢谢大家，请问看什么书才有各种算法的设计呀，我是说除了那些基本的算法，

sdnd2000 发表于 2008-4-12 21:49

这个程序时间复杂度应该是n方吧，要求用O（n）设计的，该怎么弄啊

卧龙孔明 发表于 2008-4-12 22:23

回ls,对于此题，可以使其复杂度达到O(N)
简单的给您写部分代码吧：
char line[MAX_SIZE]={0};
int i;
for(i=0;i<SIZE_A;i++)
{
  line[A[i]]=1;
}
for(i=89;i>45;i--)
{
  if(line[i]&&line[90-i]) printf("%d %d\n",i,90-i);
}

[[it] 本帖最后由 卧龙孔明 于 2008-4-12 22:27 编辑 [/it]]

卧龙孔明 发表于 2008-4-12 22:24

以上为算法就是我说的背包

sdnd2000 发表于 2008-4-13 04:13

版主真是牛人啊

页: [1]

编程论坛