商店促销活动中的付费问题.docx
《商店促销活动中的付费问题.docx》由会员分享，可在线阅读，更多相关《商店促销活动中的付费问题.docx（24页珍藏版）》请在冰点文库上搜索。
商店促销活动中的付费问题
题目：
（商店促销活动中的付费问题）设计程序完成如下要求：
某商店促销中为顾客提供各种优惠，把若干种商品分成一组降价销售。
例如一朵花原价2元，一只花瓶原价5元，而用优惠券可以用5元买3朵花，用10元买2只花瓶加一朵花，这时顾客买3朵花和2只花瓶只须付14元－用第2种优惠组合买2只花瓶加1朵花，再用原价买2朵花，所付费用最少。
试编写程序帮助收银员计算顾客所购商品应付的最少费用。
假定顾客手中的优惠券都有充分多张，可将同一种券反复用多次。
设计提示：
输入由两个部分组成，第一部分是100种商品的名称和价格，第二部分是若干组测试数据，每组测试数据包含一张优惠券的N种组合优惠的描述和顾客的购物清单，N一般不超过20，每一种优惠组合所涉及的不同商品数不超过6件。
输出为对每一组测试数据，输出顾客应付的最小费用。
可采用对各种优惠组合做深度优先遍历或动态规划法求解。
一、问题分析和任务定义
问题分析：
此程序需要完成如下要求：
在一组促销类商品中，规定一些优惠组合方案，对任意购买的一组商品（在促销范围内），均能选择出一些合适的优惠方案组合，使得顾客所购买商品应付的费用最少，并最终输出所买商品调用优惠方案的使用次数及总费用。
任务定义：
实现本程序需要解决以下的几个问题：
1.怎样存储优惠方案及其组合。
2.如何调用优惠方案。
3.怎样实现对各种方案的遍历。
4.如何实现查找的过程。
5.将各种使用优惠方案的次数输出。
问题的关键和难点在于各种优惠组合的求解、存储和遍历。
根据问题的分析，可采用树及相关的操作来解决这些问题。
对于优惠组合的存储采用链接存储，可用孩子表示法建立一棵树每一结点对应一种优惠方案的价格，同时也要实现对各种优惠组合做先序优先遍历（利用孩子表示法），以及查找某一结点操作功能。
设计要求：
a、优惠方案自己设定。
b、求的购买商品的最小值。
c、相关的数据用数组来存储。
d、优惠方案的存储用树来存储。
e、方案组合使用的次数用先序遍历。
数据的输入形式和输入值的范围：
树的建立过程中，其结点的数据域为整数，在遍历树的过程中要用到查找操作，在查找的过程需要传送输入元素的值，所有数据元素的类型都是整型。
结构的输出形式：
在所有的操作中都要判断操作是否正确显示正确的结果，在计算出所有商品的费用后，显示最终的结果内容。
二、数据结构的选择和概要设计
1、数据结构的选择：
解决这些问题，需要用到以下的数据结构来存储相关的数据：
优惠方案的组合用树型结构来存储，商品数量的备份，优惠策略的记录和存储都需要用到一维数组。
其它非促销类商品定义一个二元组a[maxlen]来存储，其中存储了商品的价格（price），数量（number）。
2、概要设计：
1）、构造一颗6层5叉树（采用孩子表示法）；2）、建立好树后，对商品的各种优惠组合做先序遍历（任采用孩子表示法）；3）、查找元素是否存在，若存在，返回元素在树中的结点位置；如不存在，返回NULL；4）在屏幕上显示操作菜单。
3、本程序包含4个函数：
①主函数main（）
②查找结点函数searchCTree（）
③建立树函数createSTree（）
④先序遍历函数preorderTree（）
4、各函数间关系如下：
searchCTree（）
createSTree（）
mainpreorderTree（）;
Goodsactive（）
List（）
图1主函数与各个子函数间的关系图
三、详细设计和编码
实现概要设计中定义的所有的数据类型，对每个操作给出相应的伪码算法
1．本程序所需用到的全局变量和相关数据类型的定义
#defineDEGREE5//规定树的度数
#defineNULL0
#definemaxlen100//a[]规定数组的最大长度
intn1,n2,n3,n4,n5;//定义商品的数量
intpr1,pr2,pr3,pr4,pr5;//定义商品的单价
inty1,y2,y3,y4,y5;//定义商品的优惠组合价格
intst1[10],st2[10],st3[10],st4[10],st5[10];//定义商品数量的备份
intg=0,d1=0,d2=0,d3=0,d4=0,d5=0;//记录优惠方案使用的次数
inty[4000],d[5],std1[5],std2[5],std3[5],std4[5],std5[5];//定义优惠策略记录数组
inttotal=0,sg[10];//定义优惠金额记录量和存储数组
2．结点类型与指针类型
typedefstructst{//树结点的类型定义
longdata;//定义数据域
structst*children[DEGREE];//指向孩子结点的指针域
}CTreeNode;
用途：
树的结点类型定义。
typedefstruct{//存储顾客购买的非促销商品内其他物品
intprice;//商品的价格
intnumber;//商品的数目
}goods,a[maxlen];
用途：
存储购买商品的价格和数目。
3．对于建立的一棵树对其结点的查找算法如下
先从树的根结点开始搜索，若data与跟结点相等，返回root;否则续查找孩子结点,若孩子结点空返回NULL，否则就递归掉用本人即returnNode=research（root->children[i],data），判断该孩子结点是否与给定的元素相等，返回returnNode;
部分代码如下：
inti;
CTreeNode*returnNode;
returnNode=（CTreeNode*）malloc（sizeof（CTreeNode））;//申请一个returnNode结点空间
if（root->data==data）//若待查找的元素与根结点相同
returnroot;//则返回根结点
else{
for（i=0;iif（root->children[i]==NULL）{
returnNULL;}//若孩子结点都为空的话，则未找到
else{
returnNode=searchCTree（root->children[i],data）;//递归调用
if（returnNode!
=NULL）{
returnreturnNode;}
4．孩子结点表示法建立一棵树
在这种方法时，每个结点不仅存储自身的数据，还存储其自身所指向的所有孩子结点的指针，结点的结构如datachild1child2child3…childd树中每个结点都包含任意多个孩子结点，一个结点中的指针域数量应为整个树的度。
先动态申请空间建立根结点root;并将其数据域赋为1，其5个孩子域赋为NULL。
同样再申请空间生成结点node其对应的孩子域也赋为NULL,然后调用secherCTree（root,m）,若其不为空，则将结点链接上去，结束，最后依次循环插入建立该棵树。
部分代码如下：
inti,j,k,m,parent;
longdata;CTreeNode*root,*parentNode,*node;
j=6;
data=1;
root=（CTreeNode*）malloc（sizeof（CTreeNode））;
root->data=data;//定义根结点元素量并赋值为1
for（i=0;ichildren[i]=NULL;
for（m=1;m<=781;m++）{//循环改变父结点指针781表示第四层最后一个元素的标号
parent=m;
for（i=2;i<=j;i++）{
data=i+5*（m-1）;//对data赋值
node=（CTreeNode*）malloc（sizeof（CTreeNode））;
node->data=data;
for（k=0;knode->children[k]=NULL;
parentNode=searchCTree（root,m）;//调用结点搜索函数
for（k=0;kif（parentNode->children[k]==NULL）{
parentNode->children[k]=node;//对空结点赋值
break;}
}
}
}
returnroot;
5．树的先序遍历算法
先序遍历主要采用递归的方法，先遍历根结点，若当j=1时，将购买的促销类商品的数目依次存放在备份数组sti[j]中，及相关信息保存为备用信息；若j处在第2层时，调用备用信息，若优惠价格与优惠记录数组相等时，记录总价格，每层依次重复进行。
接着依次遍历孩子结点，等孩子结点遍历结束时退出遍历最后在对孩子结点递归调用如：
preorderTree（ctchild）。
其C语言的代码如下：
j=ctroot->data;//先序遍历根结点
if（j>=2&&j<=6）{
n1=st1[5];n2=st2[5];n3=st3[5];n4=st4[5];n5=st5[5];g=sg[5];
d1=std1[5];d2=std2[5];d3=std3[5];d4=std4[5];d5=std5[5];}//调用备份信息
if（j>=7&&j<=31）{
n1=st1[4];n2=st2[4];n3=st3[4];n4=st4[4];n5=st5[4];g=sg[4];
d1=std1[4];d2=std2[4];d3=std3[4];d4=std4[4];d5=std5[4];}
if（j>=32&&j<=156）{
n1=st1[3];n2=st2[3];n3=st3[3];n4=st4[3];n5=st5[3];g=sg[3];
d1=std1[3];d2=std2[3];d3=std3[3];d4=std4[3];d5=std5[3];}
if（j>=157&&j<=781）{
n1=st1[2];n2=st2[2];n3=st3[2];n4=st4[2];n5=st5[2];g=sg[2];
d1=std1[2];d2=std2[2];d3=std3[2];d4=std4[2];d5=std5[2];}
if（j>=782&&j<=3907）{
n1=st1[1];n2=st2[1];n3=st3[1];n4=st4[1];n5=st5[1];g=sg[1];
d1=std1[1];d2=std2[1];d3=std3[1];d4=std4[1];d5=std5[1];}
if（y[j]==y1&&n1>=3）{n1=n1-3;g=g+y[j];d1++;}
if（y[j]==y2&&n1>=1&&n2>=2）{n1=n1-1;n2=n2-2;g=g+y[j];d2++;}
if（y[j]==y3&&n3>=6）{n3=n3-6;g=g+y[j];d3++;}
if（y[j]==y4&&n4>=4&&n5>=2）{n4=n4-4;n5=n5-2;g=g+y[j];d4++;}
if（y[j]==y5&&n3>=4&&n4>=3&&n5>=3）{n3=n3-4;n4=n4-3;n5=n5-3;
g=g+y[j];d5++;}
if（total>g+n1*pr1+n2*pr2+n3*pr3+n4*pr4+n5*pr5）{
total=g+n1*pr1+n2*pr2+n3*pr3+n4*pr4+n5*pr5;d[1]=d1;d[2]=d2;d[3]=d3;
d[4]=d4;d[5]=d5;}//优惠金额与原价比较
if（j>=157&&j<=781）{
st1[1]=n1;st2[1]=n2;st3[1]=n3;st4[1]=n4;st5[1]=n5;sg[1]=g;std1[1]=d1;
std2[1]=d2;std3[1]=d3;std4[1]=d4;std5[1]=d5;}
if（j>=32&&j<=156）{
st1[2]=n1;st2[2]=n2;st3[2]=n3;st4[2]=n4;st5[2]=n5;sg[2]=g;std1[2]=d1;std2[2]=d2;std3[2]=d3;std4[2]=d4;std5[2]=d5;}
if（j>=7&&j<=31）{
st1[3]=n1;st2[3]=n2;st3[3]=n3;st4[3]=n4;st5[3]=n5;sg[3]=g;std1[3]=d1;
std2[3]=d2;std3[3]=d3;std4[3]=d4;std5[3]=d5;}
if（j>=2&&j<=6）{
st1[4]=n1;st2[4]=n2;st3[4]=n3;st4[4]=n4;st5[4]=n5;sg[4]=g;std1[4]=d1;
std2[4]=d2;std3[4]=d3;std4[4]=d4;std5[4]=d5;}
if（j==1）{
st1[5]=n1;st2[5]=n2;st3[5]=n3;st4[5]=n4;st5[5]=n5;sg[5]=g;std1[5]=d1;
std2[5]=d2;std3[5]=d3;std4[5]=d4;std5[5]=d5;}//保存为备份信息
for（i=0;ictchild=ctroot->children[i];
if（ctchild==NULL）break;//遇到空结点则遍历结束/孩子结点遍历结束，退出
else
preorderTree（ctchild）;//递归调用自身进行先序遍历
}
6．优惠策略的生成。
自定义优惠方案，输入促销类商品的类目表及价格，生成优惠策略，并显示出来。
7．顾客购物清单。
输入促销类商品购买的情况，即商品所的数量。
注意各个商品数量的输入范围都大于0小于10，若输入的不在该范围内，则重新输入，最后输出商品未优惠前的总价。
其代码如下：
printf（"\t\t###########商品促销活动中的付费问题###########\n\n"）;
printf（"\t\t\t\t欢迎使用\n"）;
printf（"促销类商品类目表如下，请输入商品的单价：
\n1.铅笔:
"）;
scanf（"%d",&pr1）;
printf（"2.水笔:
"）;
scanf（"%d",&pr2）;
printf（"3.钢笔:
"）;
scanf（"%d",&pr3）;
printf（"4.小刀:
"）;
scanf（"%d",&pr4）;
printf（"5.橡皮:
"）;
scanf（"%d",&pr5）;
y1=pr1*3-1;y2=pr2*2;y3=pr3*5;y4=pr4*3+pr5*2;y5=pr3*2+pr4*2+pr5*3;
printf（"根据单价，系统自动生成优惠方案:
"）;
printf（"\n买铅笔*3的价格为:
%d",y1）;
printf（"\n买铅笔*1+水笔*2的价格为：
%d",y2）;
printf（"\n买钢笔*6的价位为:
%d",y3）;
printf（"\n买小刀*4+橡皮*2的价格为:
%d",y4）;
printf（"\n买钢笔*4+小刀*3+橡皮*3的价格为：
%d",y5）;
8．设计主函数模块voidmain（）
主函数模块代码：
{printf（"〓☆☆☆☆☆☆☆☆☆商店促销活动中的付费问题☆☆☆☆☆☆☆☆〓\n\n"）;
printf（"欢迎使用本系统：
\n\n"）;
Goodsactive（）;
list（）;
printf（"请稍候......\n"）;
y[0]=0;y[1]=0;y[2]=y1;y[3]=y2;y[4]=y3;y[5]=y4;y[6]=y5;
for（inti=7;i<10000;i++）{
y[i]=y[i-5];
}
CTreeNodeTr,*Tree=&Tr;
Tree=createSTree（）;
preorderTree（Tree）;
d1=d[1];d2=d[2];d3=d[3];d4=d[4];d5=d[5];
printf（"▲调用优惠方案的情况:
"）;
printf（"\n第一种方案使用了%d次",d1）;
printf（"\n第二种方案使用了%d次",d2）;
printf（"\n第三种方案使用了%d次",d3）;
printf（"\n第四种方案使用了%d次",d4）;
printf（"\n第五种方案使用了%d次\n",d5）;//输出优惠策略
printf（"在优惠活动中最少所需付费为：
"）;//输出优惠商品总金额
printf（"%d元\n",total）;
printf（"▲请输入非促销类商品的信息：
\n"）;
intn,p=0;printf（"请输入商品的个数n：
"）;
scanf（"%d",&n）;
goodsa[maxlen];
for（i=0;i{printf（"商品的单价、数量:
"）;
scanf（"%d%d",&a[i].price,&a[i].number）;
p=p+a[i].number*a[i].price;
}
total=total+p;
printf（"购买所有商品所需付的总费用是:
"）;
printf（"%d\n\n",total）;//输出最终金额
printf（"〓☆☆☆☆☆☆☆☆☆☆谢谢惠顾!
☆☆☆☆☆☆☆☆☆☆☆〓\n"）;
}
四、上机调试
1．上机调试遇到的问题及修改：
在本程序中在先序遍历树和查找某一元素时，使用了递归的思想进行查找和遍历，程序相对比较简单，语句不多。
在调试过程中常遇到问题主要在于子函数和变量的定义，关键字和函数名称的书写，以及一些库函数的规范使用。
尤其是分析怎么去把优惠方案放入树中，怎样去调用优惠方案组合等。
比如我在使用goto语句时就出现过错误，不过这些问题都可以根据编译器的警告和提示，相应将其解决。
语法错误及修改：
在本算法中我利用递归的思想进行遍历，所以程序比较简单，语句相对比较少。
而在程序中所出现的错误主要在子函数和变量的定义，括号的配对，关键字和函数的名称的书写，而这些问题在编写程序运行时就可以一一的解决。
2．时间和空间的性能分析
本程序所需的空间复杂度相对不太高，时间复杂度较高。
查找路径的时间复杂度最坏的情况下时间复杂度为O（nn），树的建立的空间复杂度为O（n），而树的遍历最坏的情况下的时间复杂度为O（nn），list和goodsactive函数的时间复杂度均为O
（1）。
综上所述要优化该算法课从树的存储结构考虑。
由于某种原因，我无法对该算法进行优化。
只是对于存放优惠策略的空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。
所以在定义时要慎重考虑，计算好后再申请。
3．算法设计调试经验和心得体会
刚拿到这个问题，自己就晕了，不知道该从何下手，总是想不太明白。
后来经过学长和同学的帮助及自己的分析总算明白了，其实不是很难的事。
对于商店促销活动中的优惠问题关键是要明白怎样存储优惠方案组合，求出最小值。
我们在进行程序设计时，要有良好的设计风格。
即要有恰当的标识符即模块名、变量名、常量名、子程序名等。
这些名字应能反映它所代表的实际东西，应有一定的实际意义，使其能够见名知意，这样有助于程序员和其他人对程序的理解。
同时在编写程序时，要对每一个程序段加上注释，这样可以有助于程序员和其他人对程序的理解，以便能熟练的操作程序。
还有在编写程序时要注意对程序的视觉组织，因为一个程序写得密密麻麻，分不出层次常常是很难看懂的。
也使得程序的正确性大大降低。
深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力，是课程设计的主要目的。
而我们所说的程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。
这是保证计算机程序正确性的必不可少的步骤。
编完计算机程序，必须送入计算机中测试。
故我们要清楚地知道程序调试该干些什么，这样才有助于我们修改程序中所存在的问题。
经过对程序的编制，使我更进一步了解树一些的基本性质，熟悉有关树的基本操作和有关商品促销问题的解决方法。
在实验的过程中也不断提高了自己的动手能力和语言组织能力，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力,当然自己在做这个程序的时候，还是存在着很多问题的，有些东西并没有完全掌握，需要自己再接再厉的去克服这些问题。
五、测试结果及分析
测试的结果符合要求，当输入数量的范围出差错时将提醒用户重新输入，同时也显示了优惠方案的调用情况和最少的费用。
六、用户使用说明
本程序运行过程中带有提示性语句，根据提示一步一步进行。
程序的编译环境是Visualc++6.0的集成化环境，其运行的环境为DOS。
调试运行时，商品促销活动中的付费问题.exe无错误和无警告的消息后，该源程序方可正确运行。
进入运行界面后，安提示语进行操作，现根据提示输入各促销商品的价格；系统会根据输入的价格自动生成优惠方案并显示。
再根据提示输入欲购买商品的数量，注意要小于10个，以减轻程序的时间复杂度。
这时，徐稍等就会出现各促销方案的调用次数与所需付费的最小费用。
最后会提示输入本次购买的非促销商品项目，然后结合促销商品的情况，得出总价钱。
七、参考文献
[1]王昆仑，李红.数据结构与算法.北京：
中国铁道出版社，2006年5月。
[2]徐孝凯，等.数据结构使用教程.北京：
清华大学出版社，2004年4月。
[3]胡学钢，数据结构.北京：
高等教育出版社，2006年9月。
[4]何钦铭，颜晖。
C语言程序设计.北京：
高等教育出版社，2008年3月。
[5]耿国华，等.数据结构：
C语言描述.西安：
西安电子科技大学出版社，2004年11月。
八、附录
源代码：
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#defineDEGREE5//规定数的度数
#defineNULL0
#definemaxlen100
/*全局变量的定义*/
intn1,n2,n3,n4,n5;//定义商品数量
intpr1,pr2,pr3,pr4,pr5;//定义商品价格
inty1,y2,y3,y4,y5;//定义商品的优惠组合价格
intst1[10],st2[10],st3[10],st4[10],st5[10];//定义商品数量的备份
intg=0,d1=0,d2=0,d3=0,d4=0,d5=0;//记录优惠方案使用的次数
inty[10000],d[5],dd1[5],dd2[5],dd3[5],dd4[5],dd5[5];//定义优惠策略记录数组
inttotal=0,sg[10];//定义优惠金额记
升级会员 