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

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

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

首先,题目是那样的:

请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。

对一个正整数n,如果n在数据文件中某行的两个正整数(假设为A和B)之间,即A<=n<=B或A>=n>=B,则n属于该行;如果n同时属于行i和j,则i和j有重叠区间;重叠区间的大小是同时属于行i和j的整数个数。

例如,行(10 20)和(12 25)的重叠区间为[12 20],其大小为9;行(20 10)和(12 18)的重叠区间为[10 12],其大小为3;行(20 10)和(20 30)的重叠区间大小为1。

输入数据:程序读入已被命名为input.txt的输入数据文本文件,该文件的行数在1到1,000,000之间,每行有用一个空格分隔的2个正整数,这2个正整数的大小次序随机,每个数都在1和2^32-1之间。(为便于调试,您可下载测试input.txt文件,实际运行时我们会使用不同内容的输入文件。) 输出数据:在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出0。

评分标准:程序输出结果必须正确,内存使用必须不超过256MB,程序的执行时间越快越好。

这是一个很简单的算法(初中的不等式知识),可以说球最大子串的一个但里面的将一个分类的思想体现的淋漓尽致。

老样子,还是第一步,分析解决问题的思路。

 一个区间是[a,b](a<b),一个区间是[c,d](c<d).    

第一步如果b<c的时候,其相连的区间是0.

第二步如果d<a的时候,其相连的区间是0。

第三步 如果a,b是c→d子链。其相连的区间是b-a+1

第四步 如果c,d是a→b子链。其相连的区间是c-d+1

第五步 如果相交的 其相连的区间是b-c+1

第六步 如果是相交 其相连的区间是d-a+1

 

那思路写出来了,源代码如下:

 1             //string 的变量
 2             string str = string.Empty;
 3             //string到 泛型数组
 4             List<string> strs=new List<string>();
 5             int i = 0;
 6             while (i<3)
 7             {
 8                 Console.WriteLine("请你输入的下列格式");
 9                 Console.WriteLine("10 20(前面的数字必须小于后面的数字)");
10                 str = Console.ReadLine();
11                 strs.Add(str);
12                 i++;
13             }
14             int count = 0;
15             int[] counts = new int[i];
16             for (int j = 0; j < strs.Count; j++)
17             {
18                 for (int k = j+1; k < strs.Count; k++)
19                 {
20                     int temp1 = Convert.ToInt32(strs[j].Split(' ')[0]);
21                     int temp2 = Convert.ToInt32(strs[j].Split(' ')[1]);
22                     int temp3 = Convert.ToInt32(strs[k].Split(' ')[0]);
23                     int temp4 = Convert.ToInt32(strs[k].Split(' ')[1]);
24                        //第一种的方法
25                     if (CheckInt(temp3,temp2)<0)
26                     {
27                         counts[count] = 0;
28                         count++;
29                     }
30                      //第二种的方法
31                     else if (CheckInt(temp4,temp1)>0)
32                     {
33                         counts[count] = 0;
34                         count++;
35                     }
36                      //第三种的方法
37                     else if (CheckInt(temp2, temp4)>=1&&CheckInt(temp3,temp1)>=1)
38                     {
39                         counts[count] = CheckInt(temp1, temp2);
40                         count++;
41                     }
42          //第四种的方法
43                     else if (CheckInt(temp2, temp4)<=1 && CheckInt(temp3, temp1) <= 1)
44                     {
45                         counts[count] = CheckInt(temp3, temp4);
46                         count++;
47                     }
48            //第五种的方法
49                     else if (CheckInt(temp2, temp4) >=1 && CheckInt(temp3, temp1) <= 1)
50                     {
51                         counts[count] = CheckInt(temp3, temp2);
52                         count++;
53                     }
54                     else if (CheckInt(temp2, temp4) <=1 && CheckInt(temp3, temp1) >= 1)
55                     {
56                         counts[count] = CheckInt(temp1, temp4);
57                         count++;
58                     }
59                 }
60             }
61                //打印情况
62             for (int j = 0; j < counts.Length; j++)
63 64                 Console.WriteLine(counts[j]);
65             }
66             Console.ReadKey();

               public static int CheckInt(int a,int b)               {                return b - a + 1;                }

 checkInt方法用来返回两个区间的之差。

 我这道题目,考虑各种的情况。 应用了分类的情况。   这个分类的思想了不光在这个题目中有了,可以说在编程过程中遍地都是。

先不来说,那个题目好吗?你看看了,编程的最基本的三种结构,顺序,选择,循环。这个选择中的无论是if.........else  结构,还是switch..................case 结构。这个结构,就是分类思想。

在比如项目中,一个登录的时候,  你要考检测用户名是否存在,  还要检测登录是否成功的情况,  如果登录不成功的情况,就跳转不同的页面。如果登录成功,又跳转到那个页面。 等等多种情况,都是要你考虑各种各样的情况。

   这就是我的一点点的感悟。

 

时间: 2022-11-17

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

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

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

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

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,看题目是那样的: 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列. 输入数据:一个正整数,以命令行参数的形式提供给程序. 输出数据:在标准输出上打印出符合题目描述的全部正

百度之星Astar2009程序设计大赛落幕

7月23日消息,由百度举办的"百度之星Astar2009程序设计大赛"在京圆满落幕.来自复旦大学的冯国栋表现出色,从两万多名参赛的程序设计高手中脱颖而出,最终捧得了"2009年百度之星"桂冠. 自2005年创办以来,"Astar百度之星程序设计大赛"已经成为中国互联网中规模最大.最具影响力的程序开发设计赛事.据主办方百度介绍,今年的大赛历时2个月,参赛选手包括清华.北大.复旦.香港中文大学等1000多所高校,以及全国百强中学的部分高中学生,这也代

百度之星Astar2009程序设计大赛落幕 复旦学子夺冠

中介交易 SEO诊断 淘宝客 云主机 技术大厅 2009年7月23日,由全球最大的中文搜索引擎百度举办的"百度之星Astar2009程序设计大赛"在京圆满落幕.来自复旦大学的冯国栋表现出色,从两万多名参赛的程序设计高手中脱颖而出,最终捧得了"2009年百度之星"桂冠. 自2005年创办以来,"Astar百度之星程序设计大赛"已经成为中国互联网中规模最大.最具影响力的程序开发设计赛事.据主办方百度介绍,今年的大赛历时2个月,参赛选手包括清华.北大.

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

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

百度之星试题每周一练

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 这个问题非常的巧,故而分享给大家,我想到一种超简单方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,题意是这样的: 八方块移动游戏要求从一个含 8 个数字 (用 1-8 表示) 的方块以及一个空格方块 (用 0 表示) 的 3x3 矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至

百度之星总冠军乔明达:编程就像玩游戏有趣

在百度之星的历届冠军选手中,乔明达无疑是一个让人大跌眼镜的存在.2013年,这个来自南京外国语学校的17岁少年将冠军宝座收入囊中,赢得了现场一片不可思议的惊叹.在以往的接触中,乔明达给我们留下的印象是一个面对镜头局促羞涩,私下却总是笑容满面,亲切的如同邻家弟弟的大男孩. 正是这个大男孩,在国内外各项赛事中都取得过令人瞩目的成绩:第5届亚洲与太平洋地区信息学http://www.aliyun.com/zixun/aggregation/34147.html">奥林匹克竞赛国际金牌(2011年

有关一道遍历算法的题目

问题描述 有关一道遍历算法的题目 有道题目,有一个点A和若干点,所有的点之间都互相可以连通,并且该连线上都有一个对应的权值,如何设计算法从A点出发遍历所有的点然后回到A点,所得到的权值和最小,并且每个点都可以经过不止一次(没C币了抱歉啊) 解决方案 这个就是迪杰斯特拉算法么,你百度一下实现方法. 解决方案二: 听来的一道算法题目一道算法题目的解法分享一道很有意思的算法题目 解决方案三: 如果这个问题每个点都只能经过一次的话就是一个标准的旅行商(TSP)问题.你可以百度下,解决方法有很多.除了楼上

继承与多态-C++一道关于继承的题目,求大神解答,感激不尽

问题描述 C++一道关于继承的题目,求大神解答,感激不尽 Dynamic_cast Total: 65 Accepted: 22 Time Limit: 1sec Memory Limit:256MB Description Three classes A, B and C are shown below: class A { public: virtual ~A() {}; }; class B: public A {}; class C: public B {}; You are to im