[FZH] 一个C语言题目

[Dee.H.Y]

有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.

但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢?
还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)

-- 
我的QQ:275471710
我的推特:dongfengweixiao
我的E_mail:[e-mail]

[microcai]

于 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 Manilone]

大家都去读编程珠玑吧。。。（首先声明我看不懂，目前的）
当然算法在一些情况下是重要的，比如珠玑的第一个案例就很实际，还有物理学之类的，图像处理之类的，效率至上。

像出这种题难住可爱的程序员的，可以去屎了。

On Sat, 14 May 2011 20:24:40 +0800 microcai <microcai(a)fedoraproject.org&gt; 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.
--------------------

[Hexchain Tong]

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

[Dee.H.Y]

这个题目我会做,就是排列组合里面的很经典的题目.不过答案貌似是一个灰常大的数字(假如拿着50块钱的人和拿着100块钱的人也要区别对待,这个数字又会更加的大了些~~~)所以貌似这个题目就是有漏洞的.

在 2011年5月14日 下午8:35，Hexchain Tong <richard0053(a)gmail.xn--com&gt;:-0s6m5392c

>  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
>  


-- 
我的QQ:275471710
我的推特:dongfengweixiao
我的E_mail:[e-mail]

[xie yunpeng]

在 2011年5月14日 下午5:08，宏羽杜 <dongfengweixiao(a)gmail.xn--com&gt;:-0s6m5392c

>  有2N个人去买票,票价是50,N个人手上有50块钱,N个人有100块钱,售票员手上没有零钱.问这2N个人有多少种排队方法.当输入一个N时,输出排列数.N<=20.
>
>  但是我不理解的是这里的排列数,到底是要输出所有的可能,还是要把每一个可能都输出呢?
>  还有就是,100的N个人和50的N个人之间是不是有差别的(即,是不是需要组合.)
没有注明不同的人，应该视为相同，应该不需要每一种排列都输出吧。感觉这种题像是从一种特定的编程问题里面抽象出来的，不知道有没有具体的编程问题需要这种算法，如果把具体的问题列出来应该会比较好理解这个算法的目的

[dhyang]

这是组合数学中的问题。用纯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;
}

[microcai]

于 2011年05月17日 14:37, David Young 写道:
>  这是组合数学中的问题 
结果是错误的。

[dhyang]

在 2011年5月17日 下午2:46，microcai <microcai(a)fedoraproject.xn--org&gt;:-0s6m5392c

>  于 2011年05月17日 14:37, David Young 写道:
>  > 这是组合数学中的问题
>
>  确实是错的，但是思路是对的，程序不够健壮，写好后没编译，也没测试，正在修改。

[Dee.H.Y]

这个题目的算法很单纯，但是结果很蛋疼。

在 11-5-17，David Young<dhyang555(a)gmail.com> 写道：
>  在 2011年5月17日 下午2:46，microcai <microcai(a)fedoraproject.xn--org&gt;:-0s6m5392c
>
> > 于 2011年05月17日 14:37, David Young 写道:
> > > 这是组合数学中的问题
> >
> > 确实是错的，但是思路是对的，程序不够健壮，写好后没编译，也没测试，正在修改。
>  _______________________________________________
>  Chinese mailing list
>  Chinese at lists.fedoraproject.org
>  https://admin.fedoraproject.org/mailman/listinfo/chinese
>  

-- 
我的QQ:275471710
我的推特:dongfengweixiao
我的E_mail:[e-mail]

[dhyang]

在 2011年5月17日 下午7:37，宏羽杜 <dongfengweixiao(a)gmail.xn--com&gt;:-0s6m5392c

>  这个题目的算法很单纯，但是结果很蛋疼。
>
>  一共出了三个问题： 
当然最大的问题是算组合数时的公式写错了，排错时才发现，第二个就是循环应该从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;
}

[Dee.H.Y]

简单的看了下,似乎是有问题的

在 2011年5月18日 上午12:45，David Young <dhyang555(a)gmail.xn--com&gt;:-0s6m5392c

>  在 2011年5月17日 下午7:37，宏羽杜 <dongfengweixiao(a)gmail.xn--com&gt;:-0s6m5392c
>
>  > 这个题目的算法很单纯，但是结果很蛋疼。
>  >
>  > 一共出了三个问题：
>  当然最大的问题是算组合数时的公式写错了，排错时才发现，第二个就是循环应该从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
>  


-- 
我的QQ:275471710
我的推特:dongfengweixiao
我的E_mail:[e-mail]

[dhyang]

在 2011年5月18日 上午8:47，宏羽杜 <dongfengweixiao(a)gmail.xn--com&gt;:-0s6m5392c

>  简单的看了下,似乎是有问题的
>
>  如果说有问题是在 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;

}

[dhyang]

在 2011年5月19日 上午12:30，David Young <dhyang555(a)gmail.xn--com&gt;:-0s6m5392c

>  在 2011年5月18日 上午8:47，宏羽杜 <dongfengweixiao(a)gmail.xn--com&gt;:-0s6m5392c
>
> > 简单的看了下,似乎是有问题的
> >
> > 如果说有问题是在 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;
>
>
>