首页 > 代码库 > 高校挑战赛：观看世界杯--限制排序算法
高校挑战赛：观看世界杯--限制排序算法
试题来源：http://student.csdn.net/mcs/programming_challenges?&page=1 观看世界杯
以前在学校参加每年的ACM程序设计大赛，感觉程序算法还是挺有意思的，这两天发现一个网站上放出一些算法试题，有点当年的那种心情，看到了，感觉能干掉，那就干掉它。目前还在公司守夜中，闲着没事就试了试算法题。
速手打，没有详细检查，可能有瑕疵请见谅，但是读题、解题、算法设计，一个不少。
if(type == 1）{...} 这段里，虽然写的有点小复杂，但是是个简单的优化，呵呵。做事前，先看清，再下手。程序猿时间有限，不要随意浪费，错误的解读，终会造成一个不正确的结果。
class Program { /* * 世界杯正在火热进行中，室友不惜睡眠时间，凌晨起来观看，但Njzy对此不是很感兴趣，他在思考一个问题： * 假设世界杯观看台上有n个座位，排成一排，游客们来到这里自由占位。一般情况下，一个游客首先考虑的座位 * 肯定是两边都没人的座位，其次考虑的是一边没人的座位，最后没得考虑，只能随便选一张两边都是人的座位。 * 假设有n个游客依次到场占位，每个人都是按照上述规则选择自己的位子，Njzy就在思考这n个游客占位的可能顺 * 序有多少种，你能帮助他？ 输入描述： 有多组测试数据，每组测试数据包括一个正整数n(0<n<1000000)。 输出 * 描述： 对于每组数据，由于答案可能会很大，所以输出：答案%1000000007 * * ************************************** * * 首先仔细读题： * 1.世界杯观看台上有n个座位，这n个座位有n个依次到场的游客来坐。 * 解析：这里面隐藏两点(这两点很重要，如果没有读出这两点，计算会非常复杂)： * a.座位数等于游客数 * b.游客有入场顺序(此题中游客的入场顺序为1,2,3,4...) * (限制型排序算法) * * * 2.首先考虑的座位肯定是两边都没人 * * 3.其次考虑的是一边没人的座位 * * 4.只能随便选一张两边都是人的座位 * * * 输出结果： * 表示游客的选座方法（顺序号对应游客的入场顺序）。 * * * 修改personIndex 的值表示入场的人数（座数），为题中n(0<n<1000000) * 如果只求出总选座的方法，可以注释 Console.WriteLine(string.Join(",", _SiteArray)); * 没有输出，提高程序的计算效率。 */ static void Main(string[] args) { //假设：人数、座位数(1,2,3...表示游客的入场顺序) int _PersonCount = 4; int[] _SiteArray = new int[_PersonCount]; int personIndex = 1; int type = 2; switch (_SiteArray.Length) { case 0: type = -1; break; case 1: type = 0; break; case 2: type = 1; break; case 3: type = 2; break; default: type = 2; break; } FuncRun(ref _SiteArray, ref personIndex, type); Console.WriteLine("总共 {0} 种选座的方法",ResCount); } static void Swap(ref int l, ref int r) { l = l ^ r; r = l ^ r; l = l ^ r; } static int ResCount = 0; static void FuncRun(ref int[] _SiteArray, ref int personIndex, int type) { if (personIndex > _SiteArray.Length) { Console.WriteLine(string.Join(",", _SiteArray)); ResCount++; return; } if (type == 2) { //--------------------------------------------------- //首先考虑的座位肯定是两边都没人 for (int i = 1; i < _SiteArray.Length - 1; i++) { if (_SiteArray[i] > 0) continue; if (_SiteArray[i - 1] == 0 && _SiteArray[i + 1] == 0) { _SiteArray[i] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[i] = 0; } } type--; } //--------------------------------------------------- //其次考虑的是一边没人的座位 if (type == 1) { if (personIndex <= 1 || _SiteArray.Length < 3) return; if (_SiteArray[0] == 0 && _SiteArray[1] == 0) { _SiteArray[0] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[0] = 0; } for (int i = 1; i < _SiteArray.Length - 1; i++) { if (_SiteArray[i] > 0) continue; if (_SiteArray[i - 1] == 0) { _SiteArray[i] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[i] = 0; } else if (_SiteArray[i + 1] == 0) { _SiteArray[i] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[i] = 0; } } if (_SiteArray[_SiteArray.Length - 1] == 0 && _SiteArray[_SiteArray.Length - 2] == 0) { _SiteArray[_SiteArray.Length - 1] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[_SiteArray.Length - 1] = 0; } type--; } //--------------------------------------------------- //只能随便选一张两边都是人的座位 if (type == 0) { for (int i = 0; i < _SiteArray.Length; i++) { if (_SiteArray[i] == 0) { _SiteArray[i] = personIndex++; FuncRun(ref _SiteArray, ref personIndex, type); //数据恢复 personIndex--; _SiteArray[i] = 0; } } } } }
高校挑战赛：观看世界杯--限制排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。