C算法编程题（七）购物

63 阅读 0 评论 42 点赞

我是靠谱客的博主含糊犀牛，最近开发中收集的这篇文章主要介绍C算法编程题（七）购物，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

　　上一篇《C算法编程题（六）串的处理》

　　有些朋友看过我写的这个算法编程题系列，都说你写的不是什么算法，也不是什么C++，大家也给我提出用一些C++特性去实现问题更方便些，在这里谢谢大家提的一些建议和意见，我当时写这个系列的目的不是探讨算法和C++的特性，可能是我标题写的不好吧，让大家误解了，再这里给大家说声抱歉。

　　大家都学过数学，做过奥数题，其实大家看看我写的前几篇文章就会发现，做这类编程题就像做奥数题一样，锻炼的是我们的逻辑思维能力，我当时写的目的也是这样。如果说用一些语言的特性去实现，那我就不用C++了，直接用C#更好的实现，用到C++只是一些简单的不能再简单的语法而已。

　　做编程题和做奥数题一样，只不过一个用数学的方式、一个用编程的方式；一个写在纸上、一个运行在电脑上；只要是思路通了，不管用什么方式都可以解决问题，只不过工具不同而已。

　　国外一些早期的牛叉编程高手都是数学家出身，所以说学好编程先学好数学。

程序描述

　　公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
   程序输入：
   第一行是一个整数m，代表可购买的商品的种类数。
   接下来是m个整数，每个1行，分别代表这m种商品的单价。
   程序输出：
       第一行是一个整数，表示共有多少种方案
       第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
   例如：
       输入：
       2
       200
       300
   则应输出：
       2
       2 2
       5 0
       输入：
       2
       500
       800
       则应输出：
       1
       2 0

程序实现

　　刚看到这个题，有点像找配对的感觉，其实做这种题就是思维能力的问题了，有的人一个小时就可以做出来，有的人哪怕做一天也做不出来。

　　这里我说一种最常用的思路，我们输入商品个数是2，单价分别为200和300，那我们先这样想，1000块最大可以200的商品是5个，最大可以买300的商品2个，只是考虑在1000块以内，买一种剩余的钱我们不考虑，所以我们可以分别找在买5个以内200的商品，看可以买300块商品有几个，就是买5个、4个、3个、2个、1个、0个200的商品，剩余的钱可以买多少个300的商品。如果加起来正好是1000块，那就是一种购买的情况。

　　思路就是这样，代码用到了一点递归的思想，我就不多说，大家自己理解下。

　　完整代码：

 1 #include"stdio.h"
 2 int a[1000];//存放商品价格
 3 int counter=0;
 4 int c[1000];
 5 int num;//商品数目
 6 void f(int b[],int i)
 7 {
 8     int j,sum=0;
 9     if(i>=num)
10     {
11         return ;
12     }
13     else
14     {
15         c[i]=1000/a[i];
16         for(b[i]=0;b[i]<=c[i];b[i]++)
17         {
18             sum=0;
19             if(i==num-1)
20             {
21                 for(j=0;j<num;j++)
22                 {
23                     sum+=b[j]*a[j];
24                 }
25                 if(sum==1000)
26                 {
27                     for(j=0;j<num;j++)
28                     {
29                         printf("%d   ",b[j]);
30                     }
31                     printf("n");
32                     counter++;
33                 }
34             }
35             else
36             {
37                 f(b,i+1);
38             }
39         }
40         return ;
41     }
42 }
43 void main()
44 {
45     int b[1000]={0};
46     int c[1000];
47 
48     int i,j,m=0,sum;
49     printf("商品数目：n");
50     scanf("%d",&num);
51     printf("商品价格：n");
52     while(m<num)
53     {
54         scanf("%d",&a[m]);
55         m++;
56     }  
57     i=0;
58     c[i]=1000/a[i];
59     for(b[i]=0;b[i]<=c[i];b[i]++)
60     {
61         f(b,i+1);
62     }
63     printf("%dn",counter);
64     getchar();
65 }