`

质数填表问题的回溯算法

 
阅读更多
<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
/**//*
标题:>应试编程实例-[分而治之算法程序设计]
作者:成晓旭
时间:2002年09月15日(11:58:00-13:18:00)
实现“装箱”问题的贪婪算法实现函数

*/

#include
"stdio.h"
#include
"stdlib.h"

//:====================“循环赛日程安排”问题的分而治之解决算法====================
/**//*
作者:成晓旭
时间:2002年09月15日(11:58:38-20:00:00)
完成“循环赛日程安排”问题的分而治之解决算法
===================================================
问题描述:
设有n(n=2^k)位选手参加网球循环赛,循环赛共进行n-1天,每位选手要与
其他n-1位选手比赛一场,且每位选手每天必须比赛一场,不能轮空。试按此要求
为比赛安排日程。

编程思想:
假设n位选手被顺序编号为1,2,3,...,n,比赛的日程表是一个n行n-1列的表格,
i行j列的表格内容是第i号选手在第j天的比赛对手。
根据分而治之的原则,可从其中一半选手(2^(n-1位)的比赛日程,导出全体n位
选手的日程,最终细分到只有两位选手的比赛日程出发。
可假设只有8位选手参赛,若1至4号选手之间的比赛日程填在日程表的左上角
(4行3列),5至8号选手之间的比赛日程填在日程表的左下角(4行3列);那么左下角的
内容可由左上角的对应项加上数字4得到。至此,剩余的右上角(4行4列)是为编号小的
1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如,在第4天,让1至4号选
手分别与5至8号选手比赛,以后各天,依次由前一天的日程安排,让5至8号选手“循环
轮转”即可。
最后,比赛日程表的右下角的比赛日程表可由,右上角的对应项减去数字
4得到。
编程图例:

===================================================================
|*|选手1天2天3天4天5天6天7天|*|
===================================================================
|*|1号|2|3|4||5|6|7|8|*|
|*|2号|1|4|3||6|7|8|7|*|
|*|3号|4|1|2||7|8|5|6|*|
|*|4号|3|2|1||8|5|6|5|*|
========[左上角]========================[右上角]===================
|*|5号|6|7|8||1|4|3|2|*|
|*|6号|5|8|7||2|1|4|3|*|
|*|7号|8|5|6||3|2|1|4|*|
|*|8号|7|6|5||4|3|2|1|*|
========[左下角]========================[右下角]===================
*/

#defineMAXN64
//日程表数组
intcalendar[MAXN+1][MAXN];
voidRound_Robin_Calendar()
...{
inti,j,m,number,p,q;
printf(
"输入选手个数:(注意:2^k) ");
scanf(
"%d",&number);
//预置两位选手的比赛日程表://第i位选手第j天与第calendar[i][j]位选手比赛
calendar[1][1]=2;//第1位选手第1天与第2位选手比赛
calendar[2][1]=1;//第2位选手第1天与第1位选手比赛
m=1;
p
=1;
while(mnumber)
...{
m
++;
//p=p+p;
p+=p;
q
=2*p;//为2^m位选手安排比赛日程
//填充日程表的左下角
for(i=p+1;iq;i++)
for(j=1;jp-1;j++)
calendar[i][j]
=calendar[i-p][j]+p;//左下角的内容=左上角的对应项加上数字4[]
//填充日程表的右上角
//填充日程表的右上角的第1列
calendar[1][p]=p+1;
for(i=2;ip;i++)
calendar[i][p]
=calendar[i-1][p]+1;
//填充日程表的右上角的其他列,参照前一列填充当前列[循环轮转算法]
for(j=p+1;jq;j++)
...{
for(i=1;ip;i++)
calendar[i][j]
=calendar[i+1][j-1];
calendar[p][j]
=calendar[1][j-1];
}

//填充日程表的右下角
for(j=p;jq;j++)
for(i=1;ip;i++)
calendar[calendar[i][j]][j]
=i;//关键语句
for(i=1;iq;i++)
...{
for(j=1;jq;j++)
printf(
"%4d",calendar[i][j]);
printf(
" ");
}

printf(
" ");
}

}

//:====================“循环赛日程安排”问题的分而治之解决算法====================

intmain(intargc,char*argv[])
...{
Round_Robin_Calendar();
printf(
" 应用程序运行结束! ");
return0;
}




Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935878


分享到:
评论

相关推荐

    素数环 回溯法——C语言代码

    课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的

    回溯算法全代码

    01背包问题 8皇后问题 堡垒问题 踩气球 迷宫问题 农场灌溉问题 求图像的周长 素数环问题 装载问题 字母转换

    素数环 回溯法-c语言

    C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码

    最快素数算法(绝非线性筛选)1.6秒算出1亿内所有素数

    革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...

    c/c++解决素数环问题

    c/c++解决素数环问题,深度优先搜索算法,算法设计与分析

    prime-number-1.zip_prime

    素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题素数填表问题

    RSA.rar_RSA算法_寻找大素数 rsa_数论算法_简单数论

    RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。...

    素数定义 素数判定证明 素数求解算法

    素数定义 素数判定证明 素数求解算法 素数定义 素数判定证明 素数求解算法

    素数测定随机算法

    素数测定随机算法 定理:如果n是素数,那么对于所有的a不恒等于0(mod n) a^n-1 恒等于 1(mod n)

    rsa素数生成及加密算法

    可以随机生成素数,并生成公钥私钥,对明文进行加密。

    大范围素数算法

    大范围的素数算法,解决素数算法的问题,当程序需要,为什么非得20个字的描述呢

    判断素数的aks算法代码matlab

    判断一个数字是素数还是合数的算法——aks算法,具有较强的优化性和较低的计算复杂度。方便、快捷、准确。

    AKS素数检测算法(多项式时间内检测)

    本资源为论文原文 当今世界上公认最新的素数判定方法 Manindra Agrawal教授和他的...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假设。

    浅析C语言中求解素数问题的算法.pdf

    浅析C语言中求解素数问题的算法.pdf

    aks算法判定素数

    Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技术研究...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假定

    java求素数的经典算法

    java求素数的经典算法java求素数的经典算法java求素数的经典算法java求素数的经典算法

    VB 设计质数判断程序及算法

    这是使用VB 设计的质数判断程序及算法, 适用于数学及科学研究。功能有: 1.输入一个数, 通过一定的算法, 判断其是否为质数。 2.给定一个范围, 导出该范围内的所有质数表。

    素数算法素数代码

    素数算法素数代码

    素数的测试算法

    素数的测试算法课程设计,讲述了素数算法的代码,还有一些想法

    简易素数算法导出的经典素数算法

    探讨不同的素数求法!从简单的素数解法入手,逐渐深入,并结合计算机的特点得到一个较为合适的素数解法!适合参加ACM竞赛的同学学习!

Global site tag (gtag.js) - Google Analytics