一道百度之星编程大赛题的随笔联想·(1)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛。他所考试的题目,全部都是算法的题目。

鄙人虽然是一个.net程序员,在工作之余,喜爱算法。 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用。

首先,看题目是那样的:

请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。

输入数据:一个正整数,以命令行参数的形式提供给程序。

输出数据:在标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列,按各序列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列,输出“NONE”。

例如,对于15,其输d出结果是:
1 2 3 4 5
4 5 6
7 8

对于16,其输出结果是:
NONE

我这里提供2种算法的解法,起一个抛砖引玉的作用

方法一:可以从后往前的计算,由大到小的计算。这种计算模式有几个思考的步骤。

①由于使 计算吗,我可以考虑从输入的数字的一半(奇数使其中间数)开始遍历。于是我就有这样一种算法。相应伪代码如图所示:

相应的源代码如下:

1        Console.WriteLine("请你输入一个数字");
 2             int mI = int.Parse(Console.ReadLine());
 3             int temp = mI;
 4            //是否能够拆成n个连续的数字的表计量
 5             bool find = false;
 6             int temp1 = 0;
 7             //记录最终的结果
 8             List<string> strs = new List<string>();
 9                //凭借成最终的字符串
10              string tempstr = string.Empty;
11              //进行循环拆解
12             for (int i = (mI - 1) / 2 + 1; i >= 1; i--)
13             {
14                 //这一元素做差了
15                 temp = temp - i;
16                 temp1 = temp;
17                 tempstr = tempstr + i.ToString()+",";
18                    //等于了有进一步做数据重置的操作
19                   if (temp == 0)
20             {
21                 tempstr = tempstr.Remove(tempstr.Length - 1);
22                 strs.Add(tempstr);
23                 find = true;
24                 tempstr = string.Empty;
25                 temp = mI;
26                 break;
27             }
28
29              }
30             //没找到可能就是空啊
31             if (!find)
32             {
33                 Console.WriteLine("None");
34             }
35             else
36             {
37                 //进行了循环遍历打印最终的结果
38                 foreach (var temps in strs)
39                 {
40                     Console.Write(mI.ToString() +
41                         "=");
42                     Console.Write(temps.Replace(",", "+"));
43                     Console.WriteLine();
44                 }
45             }
46             Console.ReadKey();

这种循环的算法固然很好,但是出现漏值的情况。譬如说

15=1+2+3+4+5

 15=4+5+6

  15=&+7

这里遗漏了15=1+2+3+4+5,我这个算法这么做固然很好啊,因为他的时间复杂度是O(n).但,我要明白这么一点的话他是以此循环,同样的数字不可能遍历2次。因此解决这个方案。必须需要两层循环。因此,必须进行方法的重构。伪代码如下:

 

相应源代码如下:

 1 Console.WriteLine("请你输入一个数字");
 2             int mI = int.Parse(Console.ReadLine());
 3             int temp = mI;
 4             bool find = false;
 5             int temp1 = 0;
 6             List<string> strs = new List<string>();
 7
 8
 9             string tempstr = string.Empty;
10
11             for (int i = (mI - 1) / 2 + 1; i >= 1; i--)
12             {
13                 temp = temp - i;
14                 temp1 = temp;
15                 tempstr = tempstr + i.ToString() + ",";
16
17                 for (int j = i - 1; j >= 1; j--)
18                 {
19                     temp = temp - j;
20                     tempstr = tempstr + j.ToString() + ",";
21                     //小于0
22                     if (temp == 0)
23                     {
24                         tempstr = tempstr.Remove(tempstr.Length - 1);
25                         strs.Add(tempstr);
26                         find = true;
27                         tempstr = string.Empty;
28                         temp = mI;
29                         break;
30                     }
31
32                     if (temp < 0)
33                     {
34                         tempstr = string.Empty;
35                         temp = mI;
36                         break;
37                     }
38                     //j==1  清空循环
39                     if (j == 1)
40                     {
41                         tempstr = string.Empty;
42                         temp = mI;
43                     }
44
45                 }
46
47
48
49             }
50
51             if (!find)
52             {
53                 Console.WriteLine("None");
54             }
55             else
56             {
57                 foreach (var temps in strs)
58                 {
59                     Console.Write(mI.ToString() +
60                         "=");
61                     Console.Write(temps.Replace(",", "+"));
62                     Console.WriteLine();
63                 }
64             }
65             Console.ReadKey();

运行效果如下所示:

这道题有效的考察了循环的知识及简单算法的题目,对初学者学习算法很有好处。

时间: 2024-03-19 16:48:49

一道百度之星编程大赛题的随笔联想·(1)的相关文章

一道百度之星编程大赛题的随笔联想·(2)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 下面介绍解法二了.  解法二,是抓小放大.  由小及大.首先,说一说我分析的思路吧.  第一步,还是判断i是不小于i/2,以此循环了.  第二步,是不是判断此范围的值的累加是不是等于相应某个值. 第三步,

百度之星编程大赛落幕六年发掘十万计算机精英

挖贝网7月28日消息 经过两个多月的激烈角逐,2010年7月28日,由百度主办的"2010 Astar百度之星程序设计大赛"正式在京落下帷幕,来自浙江大学的杭航表现出色,从三万多名参赛的程序设计高手中脱颖而出,最终捧得"2010年百度之星"桂冠.而在其余8名二.三等奖获得者中,山东师大附中魏铭等几位高中生的身影,也成为当天比赛的一大亮点. 作为中国互联网中规模最大.最具影响力的程序开发设计赛事,"Astar百度之星程序设计大赛"自2005年创办来

2009百度之星程序设计大赛启动

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 5月5日,a*star2009百度之星程序设计大赛,以"Code人心弦"为宣传口号全面启动. 据悉,从5月5日到5月29日,均可在大赛官网注册.大赛官网包含赛事规则.赛题集锦.答题指南等详细信息,选手可在此处了解最新消息,为比赛做充分准备. 整个赛事一直延续到2009年7月中旬,包括5月底的网络资格赛(初赛).6月中旬的网

百度之星程序设计大赛开幕

5月20日,百度举办的"2011Astar百度之星程序设计大赛"(http://star.baidu.com/)面向全国高校学生和广大编程爱好者拉开帷幕.本届"Astar大赛"除延续往届的赛程及奖励办法外,还将特别增设不少激烈而极具趣味的"关卡",让众多热爱编程的年轻"极客"们能充分展现自我,从实战中快速获得提升. 已经成功举办六届的"Astar百度之星程序设计大赛"是国内参赛人数最多.影响力最大的程序赛事

10年百度之星编程赛复赛题目(蜗牛)求答案代码

问题描述 10年百度之星编程赛复赛题目(蜗牛)求答案代码 ?一只蜗牛某天早晨掉进了深为L尺的井中.蜗牛每天白天可以向上爬若干尺,晚上休息时会向下滑若干尺.蜗牛一旦 到达井口或井底,便不再下滑.假设蜗牛每天向上爬的尺数均为不超过10的正整数,而下滑的尺数为不超过5的正整数.蜗牛在第N天白天里(含第N天白天结束时)爬出了井,你的任务是统计有多少种可能的爬升/下滑情况.对于两种爬升/下滑情况,当存在对应的白天上爬或者晚上下滑的尺数不同时,即视为不同的情况.输入格式第一行:井深L.其中L为正整数,且L<

第五届“Astar百度之星程序设计大赛”正式向全国高校学生启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

第五届Astar百度之星程序设计大赛启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

由一道百度之星题目写起 谈谈编程中的分类的思想

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个非主流的.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 更重要想谈一谈算法中的分治算法. 首先,题目是那样的: 请编写程序,找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小. 对一个正整数n,如果n在数据文件中某行的两个正

2012“Astar百度之星”大赛启动

近日,"Astar百度之星"编程大赛在清华大学拉开帷幕,旨在让编程爱好者们通过自己擅长的程序代码,获得"改变世界的荣耀感".据悉,本次资格赛的参赛人数将挑战全球"同时参与人数最多的在线编程"纪录,在大赛中脱颖而出的选手还将进入百度公司校园招聘"绿色通道",直接获得加盟百度的优先通行证,与世界顶级工程师共事.同时,本届Astar百度之星还将"公益编程大赛"作为辅线赛事,号召参赛者共同关注社会问题.另外,&qu