<iframe align="center" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
//质数填表问题处理头文件
//质数填表问题的回溯算法
/**//*
作者:成晓旭
时间:2001年10月9日(15:00:38-16:00:00)
内容:完成质数填表问题的回溯算法
===================================================
问题描述:
在9(3*3)个方格的方阵中填入数字1-N(N>=10)内的某9个数字,
每个方格填一个整数,使所有相邻两个方格内的两个整数之和为质
数.
编程思想:
{
intm=8,ok=1;
intn=8;
do
{
if(ok)
{
if(m==n)
{
输出解;
调整;
}
else
扩展;//向前试探
}
else
调整;//向后回溯
ok=检查前m个整数填写的合理性
}while(m!=0)
}
*/
#include"stdlib.h"
#defineMAXN100
#defineN12
intpnumber[MAXN];
intflag[N+1];
intcheckMatrix[][3]=...{...{-1},...{0,-1},...{1,-1},...{0,-1},...{1,3,-1},...{2,4,-1},...{3,-1},...{4,6,-1},...{5,7,-1}};
//显示输入填写的数字
voidPrintSetPrimeNumber(intarray[])
...{
inti,j;
for(i=0;i3;i++)
...{
for(j=0;j3;j++)
printf("%4d",array[3*i+j]);
printf(" ");
}
scanf("%*c");
}
//判断自然数是否是质数
intIsPrimeNumber(intm)
...{
inti;
intprimes[]=...{2,3,5,7,11,13,17,19,23,29,-1};
if((m==1)||(m%2==0))return(0);/**//*非质数*/
for(i=0;primes[i]>0;i++)
if(m==primes[i])return(1);/**//*质数*/
for(i=3;i*im;)
...{
if(m%i==0)return(0);/**//*非质数*/
i+=2;
}
return(1);/**//*质数*/
}
//选择下一个要试探填写的自然数
intSelectNumber(intstart)
...{
inti;
for(i=start;iN;i++)
if(flag[i])return(i);
return(0);
}
//查测当前位置的插入数据是否合理
intCheck(intpos)
...{
inti,j;
if(pos0)return(0);
for(i=0;((j=checkMatrix[pos][i])>=0);i++)
if(!IsPrimeNumber(pnumber[pos]+pnumber[j]))return(0);
return(1);
}
intExtend(intpos)
...{
pnumber[++pos]=SelectNumber(1);
flag[pnumber[pos]]=0;
return(pos);
}
intChange(intpos)
...{
intj;
while((pos>=0)&&(j=SelectNumber(pnumber[pos]+1))==0)
flag[pnumber[pos--]]=1;
if(pos0)return(-1);
flag[pnumber[pos]]=1;
pnumber[pos]=j;
flag[j]=0;
return(pos);
}
voidFind()
...{
intok=1,pos=0;
pnumber[pos]=1;
flag[pnumber[pos]]=0;
do
...{
if(ok)
...{
if(pos==8)
...{
PrintSetPrimeNumber(pnumber);/**//*输入填写结果*/
pos=Change(pos);/**//*调整下一个将填入的自然数*/
}
else
pos=Extend(pos);/**//*扩展填写范围*/
}
else
pos=Change(pos);/**//*调整下一个将填入的自然数*/
ok=Check(pos);
}while(pos>=0);
}
分享到:
相关推荐
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
01背包问题 8皇后问题 堡垒问题 踩气球 迷宫问题 农场灌溉问题 求图像的周长 素数环问题 装载问题 字母转换
本资源为论文原文 当今世界上公认最新的素数判定方法 Manindra Agrawal教授和他的...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假设。
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...
c/c++解决素数环问题,深度优先搜索算法,算法设计与分析
素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题
RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。...
素数定义 素数判定证明 素数求解算法 素数定义 素数判定证明 素数求解算法
素数测定随机算法 定理:如果n是素数,那么对于所有的a不恒等于0(mod n) a^n-1 恒等于 1(mod n)
可以随机生成素数,并生成公钥私钥,对明文进行加密。
大范围的素数算法,解决素数算法的问题,当程序需要,为什么非得20个字的描述呢
判断一个数字是素数还是合数的算法——aks算法,具有较强的优化性和较低的计算复杂度。方便、快捷、准确。
浅析C语言中求解素数问题的算法.pdf
Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技术研究...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假定
java求素数的经典算法java求素数的经典算法java求素数的经典算法java求素数的经典算法
这是使用VB 设计的质数判断程序及算法, 适用于数学及科学研究。功能有: 1.输入一个数, 通过一定的算法, 判断其是否为质数。 2.给定一个范围, 导出该范围内的所有质数表。
素数算法素数代码
素数的测试算法课程设计,讲述了素数算法的代码,还有一些想法
探讨不同的素数求法!从简单的素数解法入手,逐渐深入,并结合计算机的特点得到一个较为合适的素数解法!适合参加ACM竞赛的同学学习!