有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢? 还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
于 2011年05月14日 17:08, 宏羽杜 写道:
有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢? 还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
为何很多人宣称学不好数学就当不好程序员呢? 因为他们狭隘的认为程序==算法
而他们又狭隘的认为算法==数学。 只因为他们遇到的算法题目都是数学题。
实际上呢? 实际上上,数学题(如果非要用计算机去解决的话)通常都是由专业的数学软件去解 决的 ....
而软件工程,则事实上不需要多少数学知识,他更多的是需要广阔的知识面,对各 种实际软件硬件的深刻理解。
拿数学题目去当习题练习编程,本身就是错误的。 好了,批判完这个,我开始解决你手头的数学题好了。
其实方法很简单,就是保证售票员手里总是有余钱就可以了。 只要手里拿 50票子的人总是在拿100票子的人之前付款,这样的排队方式就是可以的。
首先我们把这类人排两队。 那么每一个队伍的排队方法是 A(N)(N) 种。
那么,典型的就是 N 个 50票子的人和 N 个 100 票子的人交错排队,保证拿 50 的在前就可以了
那么可能的情况就是 A(N)(N) * A(N)(N) . 分别是 两队 N 个人员的完全排列 再对这2个完全排列的进行组合。
但是,这还只是其中的一种情况。
事实上, 这2队人可以任意穿插,只要在穿插的时候,保证 50 票子那队的人先行 排队。
这样算出来排列的可能性就可以用一个公式表达出来了。 诶,好几年没学数学 了,都不知道接下来怎么排了。囧,请知道的人赶紧站出来指点一下。
反正,只要一个公式折腾出来就可以了,程序也就是一个简单的计算过程, 按按计算器就可以了。
= =
我说到,公式出来了,按按计算器就可以了,我是这么说的么? 呵呵。
所以啊,解决数学问题不是程序员的事情,编写好用的计算器软件才是。
国内的教育都在误导程序员去做数学家。
而编写计算器软件,则更多的是艺术~~~~~~ 而不是数学。
so, knuth 说, 计算机科学首先艺术。
大家都去读编程珠玑吧。。。(首先声明我看不懂,目前的) 当然算法在一些情况下是重要的,比如珠玑的第一个案例就很实际,还有物理学之类的,图像处理之类的,效率至上。
像出这种题难住可爱的程序员的,可以去屎了。
On Sat, 14 May 2011 20:24:40 +0800 microcai microcai@fedoraproject.org wrote:
于 2011年05月14日 17:08, 宏羽杜 写道:
有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢? 还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
为何很多人宣称学不好数学就当不好程序员呢? 因为他们狭隘的认为程序==算法
而他们又狭隘的认为算法==数学。 只因为他们遇到的算法题目都是数学题。
实际上呢? 实际上上,数学题(如果非要用计算机去解决的话)通常都是由专业的数学软件去解 决的 ....
而软件工程,则事实上不需要多少数学知识,他更多的是需要广阔的知识面,对各 种实际软件硬件的深刻理解。
拿数学题目去当习题练习编程,本身就是错误的。 好了,批判完这个,我开始解决你手头的数学题好了。
其实方法很简单,就是保证售票员手里总是有余钱就可以了。 只要手里拿 50票子的人总是在拿100票子的人之前付款,这样的排队方式就是可以的。
首先我们把这类人排两队。 那么每一个队伍的排队方法是 A(N)(N) 种。
那么,典型的就是 N 个 50票子的人和 N 个 100 票子的人交错排队,保证拿 50 的在前就可以了
那么可能的情况就是 A(N)(N) * A(N)(N) . 分别是 两队 N 个人员的完全排列 再对这2个完全排列的进行组合。
但是,这还只是其中的一种情况。
事实上, 这2队人可以任意穿插,只要在穿插的时候,保证 50 票子那队的人先行 排队。
这样算出来排列的可能性就可以用一个公式表达出来了。 诶,好几年没学数学 了,都不知道接下来怎么排了。囧,请知道的人赶紧站出来指点一下。
反正,只要一个公式折腾出来就可以了,程序也就是一个简单的计算过程, 按按计算器就可以了。
= =
我说到,公式出来了,按按计算器就可以了,我是这么说的么? 呵呵。
所以啊,解决数学问题不是程序员的事情,编写好用的计算器软件才是。
国内的教育都在误导程序员去做数学家。
而编写计算器软件,则更多的是艺术~~~~~~ 而不是数学。
so, knuth 说, 计算机科学首先艺术。
-------------------- Mike is here. My OS: Fedora x64 My blog: www.ekd123.org [Powered by Chito] My favorite editor: Emacs 23.2 My E-mail client: Mew 6.3 on Emacs 23.2. --------------------
这个题目我会做,就是排列组合里面的很经典的题目.不过答案貌似是一个灰常大的数字(假如拿着50块钱的人和拿着100块钱的人也要区别对待,这个数字又会更加的大了些~~~)所以貌似这个题目就是有漏洞的.
在 2011年5月14日 下午8:35,Hexchain Tong richard0053@gmail.com写道:
On 05/14/2011 05:08 PM, 宏羽杜 wrote:
有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢?
排列数是一个数字,表示有多少种排列。
还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
N个“拿着100元的人”和N个“拿着50元的人”
-- Hexchain Tong _______________________________________________ Chinese mailing list Chinese at lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/chinese
在 2011年5月14日 下午5:08,宏羽杜 dongfengweixiao@gmail.com写道:
有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢? 还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
没有注明不同的人,应该视为相同,应该不需要每一种排列都输出吧。感觉这种题像是从一种特定的编程问题里面抽象出来的,不知道有没有具体的编程问题需要这种算法,如果把具体的问题列出来应该会比较好理解这个算法的目的
这是组合数学中的问题。用纯C写一下。 #include <stdio.h> int fab(int number) { if(number>0) return fab(number-1)*number; else if(number=0) return 1; return -1; } int comb(int number,int count) { if((count<=number)&&(number<=20)&&(number>0)) return (fab(number)/fab(number-count)); return -1; }
int main() { int sum=0,count,number; scanf("%d",&number); for(count=1;count<number;++count) {
sum+=comb(number,count);
}
printf("the result is:%-d\n",sum); return 0; }
在 2011年5月17日 下午2:46,microcai microcai@fedoraproject.org写道:
于 2011年05月17日 14:37, David Young 写道:
这是组合数学中的问题
确实是错的,但是思路是对的,程序不够健壮,写好后没编译,也没测试,正在修改。
这个题目的算法很单纯,但是结果很蛋疼。
在 11-5-17,David Youngdhyang555@gmail.com 写道:
在 2011年5月17日 下午2:46,microcai microcai@fedoraproject.org写道:
于 2011年05月17日 14:37, David Young 写道:
这是组合数学中的问题
确实是错的,但是思路是对的,程序不够健壮,写好后没编译,也没测试,正在修改。
Chinese mailing list Chinese at lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/chinese
在 2011年5月17日 下午7:37,宏羽杜 dongfengweixiao@gmail.com写道:
这个题目的算法很单纯,但是结果很蛋疼。
一共出了三个问题:
当然最大的问题是算组合数时的公式写错了,排错时才发现,第二个就是循环应该从0开始,第三个问题是,==错写成=. Version 2.0版如下: #include <stdio.h> int fab(int number) { if(number>0) return fab(number-1)*number; else if(number==0) return 1; return -1; } int comb(int number,int count) { int a,b,c; a=fab(number); b=fab(count); c=fab(number-count); if((a<0)||(b<0)||(c<0)) return 0; else return a/b/c; }
int main() { int sum=0,count,number; scanf("%d",&number); number--; for(count=0;count<=number;++count) { sum+=comb(number,count); }
printf("the result is:%-d\n",sum); return 0; }
简单的看了下,似乎是有问题的
在 2011年5月18日 上午12:45,David Young dhyang555@gmail.com写道:
在 2011年5月17日 下午7:37,宏羽杜 dongfengweixiao@gmail.com写道:
这个题目的算法很单纯,但是结果很蛋疼。
一共出了三个问题:
当然最大的问题是算组合数时的公式写错了,排错时才发现,第二个就是循环应该从0开始,第三个问题是,==错写成=. Version 2.0版如下: #include <stdio.h> int fab(int number) { if(number>0) return fab(number-1)*number; else if(number==0) return 1; return -1; } int comb(int number,int count) { int a,b,c; a=fab(number); b=fab(count); c=fab(number-count); if((a<0)||(b<0)||(c<0)) return 0; else return a/b/c; }
int main() { int sum=0,count,number; scanf("%d",&number); number--; for(count=0;count<=number;++count) { sum+=comb(number,count); }
printf("the result is:%-d\n",sum); return 0;
} _______________________________________________ Chinese mailing list Chinese at lists.fedoraproject.org https://admin.fedoraproject.org/mailman/listinfo/chinese
在 2011年5月18日 上午8:47,宏羽杜 dongfengweixiao@gmail.com写道:
简单的看了下,似乎是有问题的
如果说有问题是在 N>=13时,int类型变量溢出,结果出错,优化算法后
Version 3.0 如下: #include <stdio.h> int main() { int N; for(N=1;N<=20;N++) { int result=1; for(num=1;num<N;num++) result<<=1; printf("N: %-3d || result: %-d\n",N,result); }
return 0;
}
在 2011年5月19日 上午12:30,David Young dhyang555@gmail.com写道:
在 2011年5月18日 上午8:47,宏羽杜 dongfengweixiao@gmail.com写道:
简单的看了下,似乎是有问题的
如果说有问题是在 N>=13时,int类型变量溢出,结果出错,优化算法后
Version 3.0 如下:
#include <stdio.h> int main() { int N; for(N=1;N<=20;N++) { int result=1,num; for(num=1;num<N;num++) result<<=1; printf("N: %-3d || result: %-d\n",N,result); }
return 0;
chinese@lists.fedoraproject.org