linux编程的108种奇易做图巧计-12(存储计算)


有时候，我们可以将计算好的值进行存储，需要的时候取出，这样可以大大降低计算量，用空间代替时间。
我们从一个问题出发，农夫John和他的朋友们一同去参加Cownty展会，这个展会的门票是50元，排队购票的人
有2n个人，其中n个人拿着100元的钞票，另外n个人拿着50元的钞票，农夫john想知道在这种情况下着2n个人共有
多少种排队的方式，使得售票处在不准备零钱的情况下，也能把票卖给这2n个人，而不会出现找不开钱的局面。
这是一个经典的组合问题，最后可以通过求解catalan数一步解决，我们这里通过深入搜索，写通项和存储计算三种方法来实现。
通过实现，存储计算的这种方法最好，但需要对计算的顺序精心设计。
在动态规划等很多场合都会用到将计算存储在一个数组中，此前的关于pfordelta的实现中也出现了将计算存储在数组中的方式，这是很常见的技巧，该问题前两种方法只所以慢一方面是因为大量重复冗余的计算，另一方面是过多的跳转，通过第三种方法改写后，计算的效率大大提高了，没有组合数学背景的同学仔细研读，应该也可以读懂，该题来自吴文虎的《程序设计中的组合数学》，实现也部分参考了这本书，但有较多不同。
#include <stdio.h>
#if defined(__i386__)
static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile ("rdtsc" : "=A" (x));
     return x;
}
#elif defined(__x86_64__)
static __inline__ unsigned long long rdtsc(void)
{
  unsigned hi, lo;
  __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
  return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
#endif

int all_n = 20;
int five_cnt = 10;
int ten_cnt = 10;
int dfs(int i,int change_cnt,int fi,int tj,int& all_cases_cnt)//fi表示拿50元钞票的人数，tj表示拿100元钞票的人数
{
        if(i == 1 )
        {
                if(change_cnt == 1&&tj==1&&fi==0)
                {
                        all_cases_cnt+=1;
                        tj-=1;
                }
                else if(change_cnt == 0&&tj==0&&fi==1)
                {
                        all_cases_cnt+=1;
                        fi-=1;
                }
        }
        else
        {
                for(int k = 0;k<2;++k)
                {
                        if(k==0)
                        {
                                if(fi>=1)
                                {
                                        dfs(i-1,change_cnt+1,fi-1,tj,all_cases_cnt);
                                }
                        }       
                        if(k==1)
                        {
                                if(tj>=1)
                                {
                                        if(change_cnt>0)
                                        {
                                                dfs(i-1,change_cnt-1,fi,tj-1,all_cases_cnt);
                                        }
                                }
                        }
                } 
        }
        
};
int f(int m,int n)
{
        if(m<n)                                      //50元的人数少于100元的人数必然无解
        {
                return 0;
        }
        else if(n==0)                            //100元的人已经不存在了，后续的都是50元的算1种
   &nbs

补充：综合编程 , 其他综合 ,