博文
建立C/C++算法群35814549(2007-04-29 10:48:00)
摘要： 最近我建立一个计算机C/C++算法的群。欢迎大家加入共同的学习35814549。......
递归完美解决"傻子造成的问题"(2007-04-28 22:28:00)
摘要：昨天晚上快睡觉的时候在这里看到了这样的一个帖子,问题是:
"100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个傻子，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。问题：最后一个上飞机的人坐到自己座位的概率是多少？？"
我对此特别感兴趣就想了一个晚上,算是找到了自己比较满意的答案0.5.虽然我看到回帖的人中有很多都说的是0.5,但是我是有我自己的解决思路,在这里拿出来和大家一起探讨一下;有什么不对的地方希望大家多指教.如果你能指出我解答之中的错误请给我指出来，送8分。
考虑一般的问题,不管一共有多少人,设为n个人,n个位置.反面考虑,和有的人一样求最后一个人(即第n个人)不能坐到自己位置的概率为P(n);设倒数第二个人不能坐到自己位置的概率为P(n-1),则P(n) = P(n - 1) + (1/(n - (n - 1) + 1)) * P(n - 1);第一个人不能坐到自己的位置的概率显然是(n-1)/n;第二个人不能坐到自己的位置的概率是:1/n (只有傻子可能坐他的位置);即这些人中第k个人(k <= n && k > 2)不能坐到自己的位置是;P(k) = P(k-1)+{1/[n-(k-1)+1]}*P(k-1);
用数学规纳法证明（我其实是通过一般的情况才看出来的这个规律）：证:最基本的情况就是当k=3的时候;第三个人的位置只可能被第一个人坐和被第二个人坐； 1.当被第一个人坐时，而第二个人坐自己的位置概率为(1/n)*1; 2.当被第二个人坐时，肯定第一个人把第二个人的位置坐了第二个人再把 三个人的位置坐了(第二个人坐的时候有n-1个位置他可以随便选)， 则概率为：(1/n)*[1/(n-1)] = {1/[n-(3-1)+1]}*P(2); 则第三个人不能坐到自己位置的概率为;(1/n)+{1/[n-(3-1)+1]}*(1/n); 即：P(3) = P(2)......
趣味算法二例（2）(2007-04-27 20:37:00)
摘要：
趣味算法二例（2）
找到了一些关于算法的趣题,现拿出来与大家分享,待其它的整理好再帖出来:
逻辑推理能力是在智力测验和智力游戏中取胜的关键，它要求人们利用已知条件，通过分析与判断，得出正确的答案。计算机解决这类问题有明显的优势，因为它具备大的存储能力，能够穷举所有可能的情形。请看下题：-----------------------------------------------------------------------------婚礼上的谎言 三对情侣参加婚礼，三个新郎为A，B，C，三个新娘为X，Y，Z，有人想知道究竟谁和谁结婚，于是就问新人中的三位，得到如下的提示：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。这人事后知道他们在开玩笑，说的全是假话，那么究竟谁与谁结婚呢？ 我们将A，B，C用数字1，2，3表示，用“X=1”表示新娘X和新郎A结婚，如果新娘X不和新郎A结婚，那么写成X！=1。用这种方法，根据新人的叙述得到如下的表达式：X！=1 A不与X结婚X！=3 C不与X结婚Z！=3 C不与Z结婚题H还隐含着的一个条件是：三个新娘不能互为配偶，则有：X！=Y且X！=Z且Y！=Z穷举所有可能的情形，代入上述表达式进行推理运算。如果假设的情况使上述表达式的结果为真，假设的情况就是正确的结果。
代码如下：#include<stdio.h>main(){ int x,y,z; for(x=1;y<=3;x++) for(y=1;y<=3;y++) for(z=1;z<=3;z++) ......
趣味算法二例(2007-04-27 20:36:00)
摘要：
趣味算法二例
中奖彩球某商场欲举办抽奖促销活动。有人建议在一个口袋中放12个乒乓球，其中三个为红色，3 个为白色，6 个为黑色，要求从中任取8个，如果满足一定的颜色组合即中奖，这样的颜色组合共有多少种？ 假设任意取出的球中红色球为i个，白色球为j个，黑色球的个数根据题意应为8-i-j个，并且红球和白球的个数取值范围是0 至3，在红球与白球个数确定的情况下黑球个数取值应为8-i-j=6.同样用穷举法，用二重循环求解这个问题。
代码如下：#include<stdio.h>main(){ int i,j,count=0; printf("\n RED BALL WH99vE BALL BLACK BALL\n"); printf("--------------------------\n"); for(i=0;i<=3;i++) /*i作为红球个数作为外层循环变量*/ for(j=0;j<=3;j++) /*j作为白球个数作为内层循环变量*/ if((8-i-j)<=6) /*如果黑球个数满足要求，打印该组合*/ printf("%2d:\t%d\t %D\n",++count,i,j,8-i......
用栈的实现排序算法。(2007-04-24 21:27:00)
摘要：// Stack Sort program in C++//----------------------用栈的方式实现排序----------------//作者：andyhou//题目：// 输入一个栈（不是数组），并且程序中只允许使用一定的整数及栈。// 结束时排序结果放在栈中，栈顶的元素最小。//算法复杂度：// 在最差情况下。算法的执行时间是@（N~2);#include <iostream>#include <stack>using namespace std;
//输入栈的函数。void EnStack(stack<int> &Astack,int n){ int item; cout<<"Enter the the data element: "; for(int i=0;i<n;i++) { cin>>item; Astack.push(item); }}//采用两个栈的方式实现栈的转换后排序。void StackSort(stack<int> &Astack,int n){ using std::stack; stack<int> Bstack; //申请一个临时的栈用来转换。 for(int i=0;i<n;i++) { for(int j=i;j<n-1;j++)//注意临界的情况。 { int temp1=Astack.top(); ......
快速排序算法的类实现(2007-04-23 22:42:00)
摘要： //Quick Sort program in C++//用类实现快速排序。#include <iostream>using namespace std;//比较类。class intCompare{public: static bool it(int x,int y) { return x<y; } static bool eq(int x,int y) { return x==y; } static bool gt(int x,int y) { return x>y; }};
template<class Record,class Compare>class Sorter{protected: static void swap(Record Array[],int i,int j);public: void printArray(Record Array[],int n);};
template<class Record,class Compare> void Sorter<Record,Compare>::swap(Record Array[],int i,int j){ Record temp=Array[i]; Array[i]=Array[j]; Array[j]=temp;}
template <class Record,class Compare>void Sorter<Record,Compare>::printArray(Record Array[],int n){ cout<<"Print all element!"; for(int i=0;i<n;i++) cout<&l......
Shell排序算法的简单实现(2007-04-22 23:36:00)
摘要：// Shell sort program in c++#include <iostream>using namespace std;
void swap(int *array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp;}//分部中的插入入排序。void middleInsertSort(int *Array,int n,int delta){ for(int i=delta;i<n;i+=delta) //是相隔一个delta进行插入排序。 for(int j=i;j>=delta;j-=delta) //与前面的几个元素比较交换。 { if(Array[j]>Array[j-delta]) swap(Array,j,j-delta); else break; //比了其中的最大的或最小的就不用再比其他元素 } ......
排列组合算法1：生成全部有序列(2007-04-21 01:56:00)
摘要：生成长度为N的全部有序列(n-tuples)
在QQ群上和朋友聊天（嗯，我还在用QQ，尽情鄙视我吧。什么时候MSN支持像QQ那样任意添加表情，任意贴图，而不是把我添加的表情图压缩得面目全非，我再放弃QQ不迟。连“彻底地全身心地毫无保留地崇拜你”都不能用，MSN my ass。QQ上的表情：
同样的图添加到MSN后： 。什么世道！），常遇到的话题之一是怎么生成一个有序列的所有组合，一个集合的所有子集（幂集），或者所有的全排列。一些论坛上也常出现类似的问题。很有意思的话题。在编程中时不时要遇到之外，也是锻炼大脑防止老年痴呆的上佳练习材料，尤其适合好静坐，喜油条， 30岁以上从不上健身房的程序员。不用左右看了。就是老大您！做这类题目还有个好处：重温当年写小程序的快乐。不知道多少人会享受搭建工资管理系统的全过程，津津有味地调试奇形怪状的API，反复修改庞杂的XML配置文件。反正我不会。写小程序就不同了。没有最后期限的压力，不用担心系统的羁绊，无需顾虑程序的架构。可以纠缠算法的每一个细节，也可以执着于提高代码的每一分性能。施主随喜。心智澄明，目光通透，心随意动，运指如飞。敲下的字符直切问题要害，摧枯拉朽。层层屏障随着代码的延伸支离破碎。写小程序解谜题的过程，就好像懵懂小孩儿扎堆游戏，纯粹为了好玩儿。一晃眼，一下午过去。他们满身泥浆，精疲力尽。但他们眼神依然兴奋，依然盼望下一次游戏。嗯，今年不收礼，收礼只收智力题。
今天又开始犯贱，万事压身就是不想动手。不过秉承拖拉也要拖有所得的原则，干脆聊聊这类问题的常用算法。
知道怎么生成全部有序列的算法，也就知道怎么生成幂集。这两者有直观的对应关系。生成全排列则另有一套算法。生成所有有序列要简单些，所以先用它开胃。当然，这类问题早有大牛写了详尽的指南， 我也就当当廉价的搬运工而已。好在还能用大牛本人的话安慰一下自己：每当发现什么有趣的问题后，轻轻Google一把，总能不幸发现有聪明人已经做出答案。
一个N-tuple是一个包含N个元素的序列，一般写作 。比如说 就是一个6-tuple。注意tuple和集合的区别。Tuple里可以包含重复的元素。而且Tuple的元素是有序的，就跟数组的元素一样。
那么给定一个N-tuple, ，我们怎么生成全部有序列呢？由简入繁总是学习的不二法门。所以我们从简单的二进......
微软过桥问题的图论解法(2007-04-21 01:40:00)
摘要： 微软过桥问题的图论解法
微软的过桥问题说的是4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？
这个问题如果用图论来建模的话，就可以以4个人在桥两端的状态来作为节点来构造一个有向图，如下图所示，以已经过桥了的人的状态作为图的节点，初始时没有人过桥，所以以空表示，第一轮有两个人过桥，有6种可能的组合，(1，2)（1，5）（1，10）（2，5）（2，10）（5，10），从空的状态转换到这些状态的需要的时间分别为2，5，10，5，10，10分钟，时间就作为有向边的权值。当有两个人过桥后，需要一个人拿手电筒回去接其他人，这时有四种可能的情况，分别是1，2，5，10中的一人留在了河的对岸，（1，2）这种状态只能转换到（1）（2）两种状态，对应的边的权值分别为2，1分钟，（1，2）转换到（1）时也就是2返回了，返回需要耗时2分钟，以此类推可以建立以下的图论模型。
要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出（空）节点到（1，2，5，10）节点间的最短路径。
根据Dijkstra最短路径算法很容易求出其最短路径，如图中的粗线所示。
这样总时间为2＋1＋10＋2＋2＝17分钟
所以能够活学图论的话，这类智力问题就变成了图论的入门级的问题。
......
二叉树和红黑树(2007-04-19 14:27:00)
摘要：
An Introduction to Binary Search and Red-Black Trees
By cpphamzaTopCoder Member
As a programmer, you'll frequently come across tasks that deal with a number of objects -- numbers, strings, people, and so forth -- and that require you to store and process those objects. If you need to maintain a list of objects that are sorted and unique, and if you need to be able to quickly insert and retrieve objects to and from this list, the ideal data structure will be a tree set (or a tree map, if you consider each object a key and associate another object called a value to it).
Many programming languages provide built-in support for tree-based sets and maps -- for instance, Java's TreeSet/TreeMap classes and the C++ Standard Template Library's set and map classes -- but because of their common use, it's easy to misunderstand what actually happens behind the scenes, and how the underlying data structures actually work. That’s what this article is all about.
We'll sta......