两道算法问题，想了很久，大家来讨论讨论吧

zihongchen 2008-06-06 09:51:51

加精

问题1：
找出满足以下条件的最小素数：
a.3个连续素数的和
b.17个连续素数的和
c.45个连续素数的和
d.979个连续素数的和
e.本身为素数

例如：41为满足以下条件的最小素数：
a.3个连续素数的和（11 ＋ 13 ＋ 17 ＝ 41）
b.6个连续素数的和（2 ＋ 3 ＋ 5 ＋ 7 ＋ 11 ＋ 13 ＝ 41）

问题2：
一个30 * 35 的表格，左上角为起点，右下角为终点，
问：从起点出发，只能向右或向下移动，到终点有几种可能。

...全文

5676 173 打赏收藏转发到动态举报

写回复

用AI写文章

173 条回复

切换为时间正序

请发表友善的回复…

发表回复

gutinglizzy 2011-07-25

打赏
举报

太厉害啦呀！

shijiemoxing 2011-07-25

打赏
举报

mark 一下先

s1120624175 2011-07-25

打赏
举报

第二题不是这样莫
1+（y -1)(x -1) = 987
看的我迷迷糊糊的
难道是没睡醒。。。

yinlu78 2011-07-09

打赏
举报

[Quote=引用 13 楼 whetu 的回复:]
mark
[/Quote]
显然是错的

风vs雷 2011-06-30

打赏
举报

第二题的，空间为n，差不多2000次加法，是我初三学qbascal时候写过这种题目，后来为了考大学，在没碰过编程，大学里简单的学了点c，好像还能记起来一点，写了下。

我在初中时候做过这种题目，当时不懂排列组合就这样想，把每一点的可能走法都写出来，然后计算下一个点的走法，因为这个人只能向左或是向右走，所以走法有a[ i ] [ j ]=a[i-1][ j ] +a[ i ][j -1];你从图中也能看出来；这样我们就能用一个二维数组将其递归出来从A到B的走法，但是从图中的分析我们发现，在程序实现时我们根本不需要这么大的空间开销（m*n），因为我们要用的数据只有要进行累加运算的那一行，除此之外，对于其他行我们根本不需使用，这样以来，我们的空间开销就只有n这么大了，我们只需定义一个大小为n的数组存储先前行的数据即可；同样我们只需做m*n步加法就能实现计算从a到b的路径个数；

这时我给出的程序：

#define MLENGH 3
#define NLENGH 5

#include <iostream>

using namespace std;

int main(){

long int tmp[NLENGH];
int i,j;
long int b;

for (j=0;j<NLENGH;j++)
{
tmp[j]=1;
}
for (i=1;i<MLENGH;i++)
{
for (j=1;j<NLENGH;j++)
{
b=tmp[j]+tmp[j-1];
tmp[j]=b;
}
}
cout<<b<<endl;
return 0;
}

非常简单，空间复杂度为（n），只需要做m*n步加法运算；

wjg945 2011-03-23

打赏
举报

第二个很简单吧

孤鸿掠影 2011-03-23

打赏
举报

第一题的那个数应该非常非常大吧？

cnmhx 2011-03-23

打赏
举报

第一题没地方用。
第二题很简单。

zhangyiese 2010-07-30

打赏
举报

#include <iostream>

using namespace std;

#define MAX_LEN 100



long long f[MAX_LEN][MAX_LEN];



int main()

{

	int m, n;

	

	while(cin>>m>>n, m!=0&&n!=0)

	{

		//dp求解, f[i][j] = f[i-1][j] + f[i][j-1] 

		for(int i = 0; i <= m; i++)

			f[i][0] = 1;

		for(int j = 0; j <= n; j++)

			f[0][j] = 1;

			

		for(int i = 1; i <= m; i++)

		{

			for(int j = 1; j <= n; j++)

			{

				f[i][j] = f[i - 1][j] + f[i][j-1];

			}

		}

		

		cout<<f[m][n]<<endl;

		

		long long result = 1; //迭代求C(m+n,n)，数值很大时有误差 

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

		{

			result *= 1.0*(n+m-i+1)/i; 

		}

		cout<<result<<endl;

	}

}

tonyliu0401 2009-02-01

打赏
举报

在想.....

noenoughmemory 2008-12-26

打赏
举报

talon1015 2008-12-26

打赏
举报

[Quote=引用 66 楼 zouyx317 的回复:]
引用 1 楼 hqin6 的回复:
第二问：

可以这么看：向右记作R、向下记作D

那么每一种都是由30个R和35个D的排列组成。

所以，共有
(30+35)!/{(30!)*(35!)}

支持

若改成：(29+34)!/{(29!)*(34!)更准确
[/Quote]

应该还是(30+35)!/{(30!)*(35!)} 可以用2*2的表格验算一下

vwxyzh 2008-12-24

打赏
举报

第一题c#控制台程序：

        static void Main(string[] args)

        {

            var sw = Stopwatch.StartNew();

            var sum = GetTheSumOfConsecutivePrime(979);

            var conditions = new[]

            {

                GetTheSumOfConsecutivePrime(3).GetEnumerator(),

                GetTheSumOfConsecutivePrime(17).GetEnumerator(),

                GetTheSumOfConsecutivePrime(45).GetEnumerator(),

            };



            foreach (var value in sum)

            {

                if (IsPrime(value) && IsMatch(value, conditions))

                {

                    sw.Stop();

                    Console.WriteLine(value);

                    Console.WriteLine("Time:{0}ms", sw.ElapsedMilliseconds);

                    Console.ReadLine();

                    return;

                }

            }

        }



        static bool IsMatch(int value, IEnumerator<int>[] conditions)

        {

            for (int i = 0; i < conditions.Length; i++)

            {

                while (true)

                {

                    if (conditions[i].Current < value)

                    {

                        conditions[i].MoveNext();

                        continue;

                    }

                    if (conditions[i].Current > value)

                        return false;

                    break;

                }

            }

            return true;

        }



        static IEnumerable<int> GetTheSumOfConsecutivePrime(int count)

        {

            Queue<int> queue = new Queue<int>(count);

            IEnumerator<int> primes = GetPrimes().GetEnumerator();

            int sum = 0;

            for (int i = 0; i < count; i++)

            {

                primes.MoveNext();

                queue.Enqueue(primes.Current);

                sum += primes.Current;

            }

            yield return sum;

            while (true)

            {

                sum -= queue.Dequeue();

                primes.MoveNext();

                queue.Enqueue(primes.Current);

                sum += primes.Current;

                yield return sum;

            }

        }



        static IEnumerable<int> GetPrimes()

        {

            yield return 2;

            yield return 3;

            int value = 5;

            while (true)

            {

                if (IsPrimeWithoutTestTwoOrThree(value))

                    yield return value;

                value += 2;

                if (IsPrimeWithoutTestTwoOrThree(value))

                    yield return value;

                value += 4;

            }

        }



        static bool IsPrime(int value)

        {

            return value % 2 != 0 && value % 3 != 0 && IsPrimeWithoutTestTwoOrThree(value);

        }



        static bool IsPrimeWithoutTestTwoOrThree(int value)

        {

            int max = (int)Math.Sqrt(value) + 1;

            int i = 5;

            while (i < max)

            {

                if (value % i == 0)

                    return false;

                i += 2;

                if (value % i == 0)

                    return false;

                i += 4;

            }

            return true;

        }

本机运行的输出为：
7419931
Time:1677ms

ahjoe 2008-12-24

打赏
举报

第一题结果: 7419931
计算用时: 253秒(AMD 2600+)

DELPHI代码: http://topic.csdn.net/u/20081224/17/d21a6f3a-a295-4bb6-8c82-fbab216abcab.html

ahjoe 2008-12-24

打赏
举报

第二题结果: 759510004936100355
计算用时: 瞬间

DELPHI代码: http://topic.csdn.net/u/20081224/17/6136bda6-ff63-45a4-a280-ed580273e62a.html

lioutou 2008-12-23

打赏
举报

mark

John_Hee 2008-12-23

打赏
举报

up!

unix_jun 2008-12-22

打赏
举报



#include <vector>

#include <iostream>



int func(int n,int m) {

	assert(n>0 && m>0);

	if (n==1 || m==1) return 1;

	typedef std::vector<std::vector<int> > MATRIX;

	MATRIX matrix(n+1,std::vector<int>(m+1));



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

		matrix[i][1]=1;



	for (int i=1;i<=m;i++) 

		matrix[1][i]=1;



	for (int i=2;i<=n;i++) 

		for (int j=2;j<=m;j++) 

			matrix[i][j] = matrix[i-1][j]+matrix[i][j-1];

		

	return matrix[n][m];

}



int main(){

	std::cout<<func(30,35)<<std::endl;

	

}