project euler 031~035

31.イギリスの硬貨のはなし。
1p,2p,5p,10p,20p,50p,100p,200pありますので200pが何通り作れるかを求める。

愚直

int maney[] = {1,2,5,10,20,50,100,200};

int main(void){
   int cnt=0;
   for(int i=0;i<200;i++)
      for(int j=0;j<100;j++)
         for(int k=0;k<40;k++)
            for(int l=0;l<20;l++)
               for(int m=0;m<10;m++)
                  for(int n=0;n<4;n++)
                     for(int o=0;o<2;o++)
                        for(int p=0;p<1;p++)
                           if(i*1+j*2+k*5+l*10+m*20+n*50+o*100+p*200 == 200) cnt++;
   cout << cnt+8 << endl;
   return 0;
}

こんなのは面白く無いので書き直し
再帰で解きました。

int money[] = {1,2,5,10,20,50,100,200};
int cnt,i;

void rec(int now,int i){
   if(now == 0){
      cnt++;
      return;
   }
   for(;i<8;i++){
      if(now >= money[i]){
         rec(now-money[i],i);
      }
   }
}

int main(void){
   cnt=0;
   rec(200,0);
   cout << cnt << endl;
   return 0;
}