博文

Josephus问题及其扩展(2005-09-19 23:41:00)

摘要:Josephus问题:
一群小孩围成一圈,任意假定一个数m,从第一个小孩起,顺时针方向数,每数到第m个小孩时,该小孩就离开,小孩不断离开,圈子不断缩小。最后,剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢?
#include
using namespace std;
void main()
{
    const int n=50;
    int child[n];
    int i,j,m,count=n;
    for(i=0;i......

阅读全文(8502) | 评论:3

2005年8月1日 第30期电脑报 编程点将(2005-08-03 02:33:00)

摘要:上周回家,那期的电脑报至今没有弄到,里面的编程点将就没有做了

题目:
一辆以固定速度行驶的汽车,司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的),为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少?新的对称数是多少

这题是我的C语言程序百例里面第22题,大家可以对比学习。

我的答案:

/*程序思想:
可以用假设两个小时的行程从1递增,当满足里程表的度数对称时停止。
按常识,两个小时后不可能使现在的里程表的度数由现在的5位数变成6位数。
故这时里程表新的值若满足个位==万位(也就是9),十位==千位就可以了。

程序在vc++6.0运行通过,结果是:

该车的速度为:50
新的对称数是:95959
*/

#include<iostream>
using namespace std;
void main()
{
    int i,a,b,c,d;
    for(i=1;;i++)
    {
        a=95859+i;
        b=a%10;//取得个位
        c=(a%100)/10;//取得十位
        d=(a/1000)%10;//取得千位
        if(b==9&&c==d)break;//个位等于9也就是万位,十位和千位相等那么这时就是对称了
&n......

阅读全文(4117) | 评论:0

2005年7月18日 第28期电脑报 编程点将(2005-09-10 21:56:00)

摘要:2005年7月18日 第28期电脑报 编程点将

上周的电脑报不知怎么回事竟然没有编程点将。可不是我忘记做了哦。

题目:已知五个互不相同的正整数之和为23,且从这五个数中挑选若干个加起来可以表示从1到23之内的全部自然数。问这五个数是什么?

这题在我的C程序设计百例的第73题,我做的结果和里面的不一样。我现在还不知道是不是我错的。我的程序并不是很简便,主要问题是验证能否组合出1到23数的那个函数上面,我现在还没有找到简便的解决方法。请给意见和建议。
我的程序:
/*算法:因为五个数互不相同且之和为23,故其中最大值不会超过13,
又因为要表示1到23之内的自然数,故必含有1和2(否则1和2无法组合出来),
因此可以假设五个数从小到大分别为:1,2,i(3-11之间),j(i+1-12之间),k(j+1—13之间).循环取得范围之内的所有可能的值,当1+2+i+j+k==23时,调用函数AA(int i,int j,int k)判断是否可以组合出1到23之内的全部自然数,是则输出。
使用C++编程,在VC++6.0中通过运行。
结果是:
第1组:1,2,3,5,12
第2组:1,2,3,6,11
第3组:1,2,3,7,10
第4组:1,2,4,5,11
第5组:1,2,4,6,10
第6组:1,2,4,7,9
*
#include<iostream>
using namespace std;
bool AA(int i,int j,int k);//函数原型,用来验证是不是可以组合出1——23的值
void main()
{    int i,j,k,count=0;
    bool a=false;

    for(i=3;i<=11;i++)
        for(j=i+1;j<=12;j++)
&nb......

阅读全文(6090) | 评论:3

2005年7月4日第26期电脑报编程点将台(2005-07-07 12:00:00)

摘要:题目:
某人有四张3分的邮票和三张5分的邮票,用这些邮票中的一张或若干张可以得到多少种不同的邮资?

这一道题就是我的C语言程序百例中的第72道,我稍微看了一下,好像我写的程序好像更简单。


/*算法分析:
从四张3分和三张5分中任取一张或若干张得到的最大邮资为27,即所得邮资3——27之间,故用数组XX[28]标志邮资是否可以得到,当某一位置的邮资可以取得时则数组在这个位置的值为1,否则为0;利用二重循环可以取所有可能的邮资值。
采用C++编程,在VC++6.0中通过运行,结果是19
*/
#include<iostream.h>
void main()
{
    int i,j,XX[28],count=0;
    for(i=0;i<28;i++)
        XX[i]=0;
    
    for(i=0;i<=4;i++)
        for(j=0;j<=3;j++)
            if(XX[3*i+5*j]==0)XX[3*i+5*j]=1;
    
    for(i=1;i<28;i++)//i从1开始取值是因为至少要从这些邮票中取一张
        if(XX[i]==1)count++;
    cout<<count<<endl;
}......

阅读全文(4696) | 评论:3

2005年第25期电脑报 编程点将台(2005-06-30 11:14:00)

摘要:在厦门就是郁闷,每周的电脑报都要到周三才可以拿到,我上次在北京的时候这周的电脑报上周六就可以拿到了啊。
昨天终于拿到报纸了,现在把里面的编程点将做出来,以享读者。
(呵呵,查了一下我的C语言程序百例,里面的第17题就是这一题,我稍微看的一下,好象我的程序比里面的简单啊 哈哈)

题目:甲、乙、丙三位渔夫出海打鱼,他们随船带了21只箩筐。当晚返航时,他们发现有七筐装满了鱼,还有七筐装满了半筐鱼,另外七筐则是空的,由于他们没有秤,只好采用目测的办法,他们认为七个满筐鱼的重量是相等的,七个半筐鱼的重量是相等的。在不将鱼倒出来的前提下,怎样将鱼和筐平分为三份?

解答:

/*编程思想:
用k1,k2分别表示第一等份的满筐筐数和半筐筐数,则其空筐筐数为:7-k1-k2;
用k3,k4分别表示第二等份的满筐筐数和半筐筐数,则其空筐筐数为:7-k3-k4;
那么第三等份的满筐筐数、半筐筐数和空筐筐数分别为:7-k1-k3,7-k2-k4,7-(7-k1-k2)-(7-k3-k4);
假设满筐时鱼为2,半筐时鱼为1,空筐时鱼为0(只是为了计算简单,数据可以成倍变化)
那么,总的鱼为21,每一份鱼为7。
所以,k1,k3<=3;循环使k1,k2,k3,k4取得所有可能的值,满足以下条件则输出:
2*k1+k2==7&&2*k3+k4==7&&(7-k1-k2)+(7-k3-k4)<7&&k3>=k1&&(7-k1-k3)>=k3
前面三个条件是控制每一份鱼和筐的数均为7,后面两个是使数据不重复输出。

使用JAVA编程,在winXP+j2sdk1.4.2_03下运行通过;
结果:第1组:第一份:满筐的筐数 1,半筐的筐数 5,空筐的筐数 1
            :第二份:满筐的筐数 3,半筐的筐数 1,空筐的筐数 3
       &nbs......

阅读全文(4704) | 评论:0

2005年6月20日 第24期电脑报 编程点将台(2005-06-26 17:30:00)

摘要:上周的电脑报因为回家到昨天才拿到报纸,把里面的编程点将做了一下,现在贴出来,以享读者。(这周的题目好像有点过分简单了,^_^)

呵呵,突然发现这道题在我收集的C语言程序百例里面的第50题就是,但里面的编码好像没有我的简单明了,大家可以比较参考一下。

题目:张三说李四在说谎,李四说王五在说谎,王五说张三和李四都在说谎。
现在问:这三人中到底谁说的是真话,谁说的是假话?

安安注:源程序写的不是很规范,其中有一语句还错了,谢谢“波涛 ”的提醒。

我的程序:

/*算法思想:
题目用整型zhs、lis、waw分别表示张三、李四和王五,
数值1表示说真话,数值0表示说谎。
由题目可知,张三和李四互逆,也就是张三说谎则李四说真,反之;
李四和王五互逆,因此lis=!zhs,waw=!lis。
采用C++编程,在VC++6.0上通过运行,
结果:李四说真话;张三和王五说假话
*/
#include<iostream>
using namespace std;
int main()
{
    int i,zhs,lis,waw;
    for(i=0;i<2;i++)
    {
        zhs=i;
        lis=!zhs;
        waw=!lis;
        if(waw==1&&zhs==0&&lis==0)//原来错了,谢谢“波涛 ”的提醒。
            cout<<"王五说真话;张三......

阅读全文(5865) | 评论:3

针对考研谈谈:伪代码的语法规则(2005-06-24 19:28:00)

摘要:现在很多大学计算机考研时,一般(甚至可以说全部)都要求要考《数据结构》,那么算法的题目基本上是必然要求的,这种题目基本上分为三种类型:
1、    写出算法的设计思想和程序
所写的程序一般要求要有基本的算法思想解释,语言一般不要求,而且可以使用伪代码甚至自然语言。
2、    程序填空,这个程序基本上都是用C/C|++写(因此我认为C++基本上是必学的语言,你可以不选择.net,但是c++至少你应该入门。
这种情况不只是考研,想高级程序员的考试、高校的必修课等等一般所要求的程序设计或者所写出来的程序基本上都是C/C++.
3、    程序和算法思想改错

下面针对第一种情况谈谈伪代码,因为考研的题目基本上是比较有难度的(特别是好的学校)而且有时间限制,因此要写出完整的程序基本上不大可能或者说不合算,因此当自己心中知道了算法思想以后用伪代码设计出来是比较好的。对于伪代码,很多书都没怎么介绍,网上的资料也不多,我以前搜藏了一篇,现在拿出来以享读者。

(以下来自网络非原创,转载的朋友也请说明)

伪代码的使用 Usage of Pseudocode

伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此,伪代码必须结构清晰,代码简单,可读性好,并且类似自然语言。

下面介绍一种类Pascal语言的伪代码的语法规则。

伪代码的语法规则
在伪代码中,每一条指令占一行(else if 例外,),指令后不跟任何符号(Pascal和C中语句要以分号结尾);
书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进;
例如:

line 1
line 2......

阅读全文(8443) | 评论:0

厦门大学2005年第二届程序设计大赛题目(2005-06-24 17:35:00)

摘要:规则:
1.赛题共五题,参赛者做出的题数将是作品评分的一个重要依据。
2.比赛作品平台不限,语言不限(推荐标准C/C++),程序占用的内存不限(只要不是太离谱),程序运行的时间不限(同样不要太离谱),但是程序编写的质量会对最后的评分有一定的影响.
3.请尽量严格按照输入输出的定义编写输入输出接口,方便多组测试样例的数据测试.当然,如果仅仅输入输出格式有问题而算法正确的程序,也同样可以得分.
4.本次比赛的目的主要是问题的分析解决,程序设计和算法设计能力,故将所有结果直接输出而没有算法分析过程的程序,就算能通过测试样例,将也一样无效.
5.理论上允许参赛者对同一份题目提供多份程序,我们可以从中帮你选出最好的,但是请尽量自行挑选一份最好的提交.请提交的时候尽量将代码整理并注释好,并提交相关设计文档.
6.虽然没有在线测试提交系统,但是由于时间上较为充分,请自行考虑编写各种情况下的测试用例,以提高你程序的准确率.
7.请独自完成,严禁代码重复,严禁相互讨论,尊重对手,也是尊重自己.
8.如对赛题有疑惑可以发邮件至: emoon11@sohu.com 征询许鹏展同学,他将热情地解答你提出的问题。

题目:
1.    取胜之道
Program国度的人,喜欢玩这样一个游戏,在一块板上写着一行数,共n个。两个游戏者,轮流从最右或最左取一个数。刚开始,每个游戏者的得分均为零。如果一个游戏者取下一个数,则将该数的值加到该游戏者的得分上,最后谁的得分最高谁就赢了游戏。给出这n个数( 从左往右), 假设游戏者都是非常聪明的,问最后两个人的得分(假设第一个人首先取数).
输入格式:第一行为n(2<=n<=100),第二行为n个数,每个数字之间均用空格隔开。输出为两个游戏者的得分.第一个数表示第一个游戏者的得分,第二个数为第二个游戏者的得分,两个数字之间用空格隔开。
如输入
6
4 7 2 9 5 2
输出
18 11

2.    分数与小数
将分数转化为小数,相信很多人都会吧.那么,这里给定一个分数N/D,N为分子,D为分母(N......

阅读全文(6533) | 评论:3