2011 蓝桥杯【初赛试题】 程序设计题二

简介:

公司发了某商店的购物券1000元,限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,,要求程序列出所有的正好能消费完该购物券的不同购物方法。

程序输入:

第一行是一个整数m,代表可购买的商品的种类数。

接下来是m个整数,每个1行,分别代表这m种商品的单价。

程序输出:

第一行是一个整数,表示共有多少种方案

第二行开始,每种方案占1行,表示对每种商品购买的数量,中间用空格分隔。

例如:

输入:

2

200

300

则应输出:

2

2 2

5 0

输入:

2

500

800

则应输出:

1

2 0

 

 

#include<stdio.h>
#include<string.h>
int cost;
int n;//物品个数 
int price[2000];//物品单价 
int num[100];//物品数目 
int sum=0;//方案数目 
int arg[100][100];//每种方案的商品分布
void Fun(int x)//递归,每件物品分为买或者不买的情况(同一物品可以买多次) 
{
    int i;
    if(cost>1000||x>=n)
    return;
    if(cost==1000)
    {
       for(i=0; i<n; i++)
         arg[sum][i] = num[i];
         sum++;
         return;

    }
    num[x]++;//选择这件商品的情况 
    cost+=price[x];
    Fun(x);//还可能继续选这件商品 
    num[x]--;//不选择这件商品的情况 
    cost-=price[x];
    Fun(x+1);//往下走 
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&price[i]);
    memset(num,0,sizeof(num));//数组清0为了之后的加减运算 
    Fun(0);
    printf("%d\n",sum);
    for(i=0;i<sum;i++)
    {
       printf("%d",arg[i][0]);//防止多输出空格 
       for(j=1;j<n;j++)
       printf(" %d",arg[i][j]);
       puts(""); 
    }

    return 0;
}

参考:http://www.cnblogs.com/hxsyl/archive/2012/12/15/2819911.html 

相关文章
|
2月前
|
人工智能 算法 Java
第十三届蓝桥杯B组Java(试题C:字符统计)
第十三届蓝桥杯B组Java(试题C:字符统计)
64 0
|
12月前
|
机器学习/深度学习 算法 C++
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
300 0
|
2月前
|
机器学习/深度学习 人工智能 算法
2024 蓝桥杯本科B组试题
2024 蓝桥杯本科B组试题
19 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-940 试题3971
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-940 试题3971
35 0
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
28 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
31 0
|
11月前
|
Java
蓝桥杯Java-B组2015年试题解题笔记
蓝桥杯Java-B组2015年试题解题笔记
|
11月前
|
数据格式
蓝桥杯Java-B组2014年试题解题笔记(下)
蓝桥杯Java-B组2014年试题解题笔记(下)
|
2月前
|
Python
第十三届蓝桥杯B组python(试题A:排列字母)
第十三届蓝桥杯B组python(试题A:排列字母)
37 0
|
2月前
|
Java
第十三届蓝桥杯B组Java(试题B:山)
第十三届蓝桥杯B组Java(试题B:山)
38 0