东北大学数据结构实验报告.doc

优质文本实 验 报 告课程名称：数据结构班级：实验成绩：实验名称：顺序表和链表的应用学号：批阅教师签字：实验编号：实验一姓名：实验日期：2017-11-25指导教师： 组号：实验时间：18:3022:30一、实验目的（1） 掌握线性表的根本操作插入、删除、查找以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。（2） 掌握线性表的链式存储结构的应用。二、实验内容与实验步骤1实验内容：实现约瑟夫环，约瑟夫环Joseph问题的一种描述是：编号为1、2、3n的n个人按照顺时针方向围坐一圈，每人持有一个密码正整数。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。2抽象数据类型和设计的函数描述，说明解决设想。首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用CreatList_CL函数来创立一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向L，使其能够形成循环队列。定义了函数Display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能，依次比拟，如果某个人所持的密码和m值相等，那么删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。（3） 简短明确地写出实验所采用的存储结构，并加以说明。 该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。三、实验环境操作系统：Windows 7调试软件名称：Visio Studio2017上机地点：信息楼B405四、实验过程与分析1主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。本实验中主要的函数包括创立链表、显示链表内容和出列过程四个局部。主要函数的代码如下：创立链表：typedef int Datatype;typedef struct node/链表的定义 Datatype data; int password; struct node *next;ListNode,*CLinkList;void CreatList_CL(CLinkList *L,int n)/创立一个链表 int i,pin; CLinkList p,q; (*L)=(CLinkList)malloc(sizeof(ListNode); if(*L)=NULL) printf("errorn"); else (*L)->next=NULL; q=*L;for(i=0;i<n;i+) p=(CLinkList)malloc(sizeof(ListNode); if(p=NULL) printf("errorn"); printf("请输入第%d个人的密码：",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin; q->next=NULL; q->next=p; q=p; q->next=(*L)->next;/指向L结点，形成 创立这个链表的时间复杂度为O(n)，空间复杂度为On2。显示链表中的信息内容：void Display(CLinkList *L,int n) int i; CLinkList p; p=(*L)->next; printf("n显示链表内容n"); for(i=0;i<n;i+) printf("编号：%2d 密码：%dn",p->data,p->password); p=p->next; 该算法的时间复杂度为On,空间复杂度为O(n2)。删除结点，完成出列功能：void Delete_L(CLinkList *L,int n,int m) int i=0,j; CLinkList p,q; q=(*L); p=(*L)->next; printf("n删除的顺序：n"); while(i<n) for(j=0;j<m-1;j+) q=p; p=p->next; printf("编号：%d 密码：%dn",p->data,p->password); m=p->password; q->next=p->next; free(p); p=q->next; n-; 该算法的时间复杂度为O(n2)，空间复杂度为O(n2)。该设计的巧妙之处在于并不需要额外的空间来存储数据，因而空间复杂度较低，而且线性表的链式存储结构可以用物理位置上的邻接关系来表示结点间的逻辑关系，这样使读者在阅读代码的过程中可以更加方便和便于理解。它可以随机存取表中的任一结点，还可以免插入和删除操作带来的大量的结点的移动，能给结点动态分配内存，这样就不存在存储空间缺乏的情况，而且循环链表还可以方便的从链表的最后一个结点遍历到链表的第一个结点。使操作更加方便。（2） 你在调试过程中发现了怎样的问题？又做了怎样的改良 1在最开始的调试阶段，我发现链表插入结束之后，不能按照正常情况下输出链表的内容，只能正常显示第一个人的数据,在显示第二个人的信息是数据为乱码。之后我发现，在插入链表的过程中，我是在执行循环插入数据的循环中将结点的指针指向了第一个结点，因而，在进行链表显示的过程中，第二个结点的内容不是正常的数据。之后我将q->next=(*L)->next;这条指令放到了整个插入循环的外部，这样表示在插入所有数据之后，最后一个结点的指针指向了第一个结点，形成了一个循环队列，此时链表的数据显示正确。2） 再次调试时，我发现人员出列时，只有第一个人出列正常，在第二个人出列时程序自动终止，不能正常显示之后出列的人的信息，并且程序自动终止运行，经过检查我发现在经过一次删除后，没有将指针指向下一个结点，因而出现问题。经过更改，程序运行正常。3） 在实验的开始阶段，数据遍历总是出现问题，经过查找资料我发现了约瑟夫环头结点的特殊性，因此我不再使用头结点，程序便恢复正常了。（2） 测试结果五、实验结果总结答复以下问题：（1） 你的测试充分吗？为什么？你是怎样考虑的？ 答：我认为我的测试充分，因为我随机选用了很多组不同的数据进行测试，并且每次测试的结果都是正确的答案，这样选取的数据具有很强的随机性，具有代表性，因而我认为我的测试比拟充分。（2） 你的存储结构的选取是不是很适合这个应用？为什么？ 答：我认为我选取的线性链式存储结构适合这个应用，因为首先此题中描述的情景中表示人们按照顺时针的方向进行排队，此时头尾相连，这与循环链表的结构十分相似，使用循环链表的结构，这样可以很方便的从链表的最后一个结点访问到链表的第一个结点，并且这样的存储方式是用物理位置上的邻接关系来表示结点间的逻辑关系，根据这个特点，该种结构可以随机存取表中的任一结点，而且它也可以防止插入和删除操作带来的大量结点的移动，并且可以随时分配空间和释放空间，这样可以减少空间的使用量，并且可以做到灵活的扩充空间，这样的结构很适合这个应用。（3） 用一段简短的代码及说明论述你的应用中有关插入和删除元素是如何做的？答：插入元素：首先定义了两个临时指针p和q来分别表示新插入结点的指针和第一个结点的指针，在每次插入之前应该动态的分配内存，输入要输入的信息，并且将各种数据存储到链表中相应的项里，将前一个结点的next赋值为空，再将前一个结点的指针指向下一个结点，此时完成一个元素的插入。依次类推，运用循环来实现所有人的数据的插入，关键代码如下： p=(CLinkList)malloc(sizeof(ListNode); if(p=NULL) printf("errorn"); printf("请输入第%d个人的密码：",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin; q->next=NULL; q->next=p; q=p; 删除元素：进行循环来实现每个元素出列的功能，首先每个人进行循环，一次进行报数，在报到m-1之前都不进行删除元素这个动作，在m时，把此时结点中的password中的数值赋给m然后运用q->next=p->next;将结点删除，同时释放结点p,将人数减1，以此类推完成所有的删除操作，直到所有的元素出列，关键代码如下：while(i<n) for(j=0;j<m-1;j+) q=p; p=p->next;printf("编号：%d 密码：%dn",p->data,p->password);m=p->password;q->next=p->next;free(p);p=q->next;n-; 4在你的应用中是否用到了头结点？你觉得使用头结点为你带来方便了吗？ 答：在我的应用中我没有用到头结点。在实验的一开始，我使用了头结点，但是使用头结点给数据的遍历带来了困难，因此我便放弃使用头结点。5源程序的大致的执行过程是怎样的？ 答：首先用编译器编写一个.c的文件，然后编译生成.obj的文件，通过连接将目 标文件连接生成一个.exe文件，之后运行文件就可以执行了。 六、附录1实验设想和建议 这次实验提高了我对数据结构中关于循环链表和顺序表的理解，提高了我的编程能力，学校以后最好可以增加实验课的课时，这样我们可以更大程度的提高自己的编程能力。另外我认为该实验不仅可以使用使用链表指针来实现，还可以使用数组来模拟链表来实现约瑟夫环，用数组的下标来指向前一个和后一个元素，之后进行删除来实现约瑟夫环。 2参考资料：?数据结构第二版? 闫玉宝编著 清华大学出版社实 验 报 告课程名称：数据结构班级：实验成绩：实验名称：栈、队列、字符串和数组学号：批阅教师签字：实验编号：实验二姓名：实验日期：2017-11-20指导教师： 组号：实验时间：18:3022:30一、实验目的1掌握栈、队列、串和数组的抽象数据类型的特征。2掌握栈、队列、串和数组的抽象数据类型在计算机中的实现方法。3学会使用栈、队列来解决一些实际的应用问题。二、 实验内容与实验步骤（1） 实验内容： 假设表达式中除了变量名、常量和运算符外，还可以允许两种括号：圆括号和中括号，其嵌套的次序随意，编写程序检验输入的表达式中括号的的顺序是否合法。（2） 描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明解决设想。抽象数据类型或函数描述：首先定义了一个结构体并且声明为栈类型，在其中定义了空间基地址的指针、栈顶指针以及栈存储空间的大小。之后设计了 Creat _Stack的函数，用此函数来创立一个空栈，这样可以使用堆栈来实现括号匹配的功能，又设计了一个名为Stack_Full的函数了来判断栈是否已满，假设栈未满才可继续之后的压栈功能，如果堆栈已满，那么需要使用realloc来动态分配空间，扩大栈的存储空间。我还设计了一个名为empty的函数，用它来判断堆栈是否为空，堆栈为空或不为空时分别返回0或1。之后设计了名为push和pop的函数来实现括号的入栈和出栈，之后设计了名为Match的函数，来判断括号是否匹配，设计了名为clean的函数来清空堆栈，这样可以连续判断不同的多项式的括号是否匹配。解决设想：对于此题，首先我使用了栈结构，利用栈中数据“先进后出的特点来实现对括号是否匹配的检验。实现过程根本如下：从左到右依次扫描多项式，如果遇到左括号便将左括号入栈，在所有左括号入栈之后便可以扫描到右括号，如果扫描到的右括号和栈顶的左括号可以匹配时，将左括号出栈，以此类推，最后判断栈是否为空，假设为空，那么括号匹配，否那么括号不匹配。三、 实验环境操作系统：Windows 7调试软件名称：Visio Studio2017上机地点：信息楼B405四、实验过程与分析1实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。主要函数或操作内部的主要算法：typedef struct/栈的声明 char *base;/指示存储数据元素的空间基地址的指针 char *top;/栈顶指针 int stacksize;/栈存储空间大小，以数据元素为单位SStack; void Creat_Stack(SStack *s)/创立空栈 s->base=(char*)malloc(sizeof(char)*size); if(s->base=NULL) printf("errorn"); else s->top=s->base; s->stacksize=size; 上面的算法用来建立栈，该算法的时间复杂度为O(1)，空间复杂度为On。int Stack_Full(SStack *s)/判断栈是否为满 if(s->top-s->base>=100) return 1; else return 0;int empty(SStack *s)/判断栈是否为空 if(s->base=s->top) return 0; else return 1;上面的算法分别用来判断栈是否已满，栈是否为空栈，上面两个算法的时间复杂度和空间复杂度均为O1。void push(SStack *s,char *str)/入栈 if(Stack_Full(s)!=0) printf("fulln"); else *s->top+=*str;void pop(SStack *s,char *str)/出栈 if(s->base=s->top) printf("The stack is emptyn"); else *str=*-s->top; 上面两个算法用来实现数据的入栈和出栈，时空复杂度均为O1。void Match(SStack *s,char *str) int i,j; char t; j=strlen(str); for(i=0;i<j;i+) if(stri='('|stri='')push(s,str); for(i=0;i<j;i+) if(stri=')') if(*s->top='(') pop(s,&t); else s->top=s->top-1; if(stri='') if(*s->top='') pop(s,&t); else s->top=s->top-1; if(empty(s)=0) printf("括号匹配!n"); else printf("括号不匹配!n");该Match函数的作用即判断括号是否匹配，是本程序的核心函数，假设假设输入的表达式的长度为n，那么此函数中进行了两次循环，一次为扫描左括号使其全部入栈，另外一次为扫描右括号并且判断新扫描出来的右括号与栈顶的左括号是否匹配。在整个过程中执行了2n次循环，因此此程序的时间复杂度为O(n)。对于空间复杂度，本算法存储了长度为n的表达式，因而该算法的空间复杂度为O(n)。设计的巧妙之处：在本程序中我使用了栈这种抽象数据类型，栈的“先进后出的特点与检验括号是否匹配的“期限待的急迫程度相吻合，设计顺序栈来解决括号匹配问题。如果单从括号检验这个目的考虑可以有多种方法来实现该实验目的，而使用栈来实现括号匹配的检测，简化了程序的设计，比拟容易理解和实现，并且可以提高时间效率。（2） 你在调试过程中发现了怎样的问题？又做了怎样的改良？1在开始程序编译时，编译器总是提醒函数的形式参数的写法有问题，之后我发现，我在栈声明时将SStack未声明为指针类型，而我在形式参数中将参数写成了SStack s，因而出现错误，所以我将其更改为SStack *s，这个问题得以解决。2之后，编译器进行编译时，编译器提醒我在调用empty，match等函数时，实际参数的输入有问题，使得编译不能够通过，经过检查我发现我在写这些函数时，形式参数定义为char *s，因而我便在实际参数中代表字符串的参数前加取地址&符号，这个问题便解决了。3在进行编译时还出现了这样的警告，说我的小于号没有定义或者没有匹配，经过检查我发现我在循环中将其中一个条件写成<strlen(str)，之后，我定义了一个新的局部变量j，用j等于str的长度，这样警告便消除了。（3） 你的抽象数据类型的实现是否具有可扩展性？我的抽象数据类型具有可扩展性，因为栈的大小可以修改，如果栈已满，那么可以增加空间，因此具有可扩展性。（4） 测试结果 五、实验结果总结答复以下问题：1你的测试充分吗？为什么？你是怎样考虑的？ 答：我认为我的测试充分，因为我的表达式是随机给出的，这样选择的数据具有随机性，具有很强的代表性，并且每次的结果正确，因此我认为我的测试比拟充分。2为什么你要选用栈或队列或字符串或数组等抽象数据类型作为你应用的数据结构？ 答：我使用了栈这种抽象数据类型作为我应用的数据结构，栈是一个只能访问表的尾端数据的数据集合，是一种在表的一端进行插入和删除操作的线性表，数据具有“先进后出的特点，而这种特点和括号匹配中检验括号的“期限待的极限程度这个特点相符合，因此选用栈这种数据结构可以简化程序，更好的理解和实现程序，提高了程序运行的时间效率。 3用一段简短的代码及说明论述你的应用中主要的函数的主要处理局部。答：下面的代码局部为Match函数中的主要处理局部，使用了两个循环来处理输入的表达式，第一个循环是用来从左到右扫描表达式遇到“或者“就将括号入栈，第二个循环是用来扫描表达式，如果遇到“或“就将其与栈顶的括号进行匹配，如果匹配，就将栈顶的左括号弹出，如果不匹配就将栈顶指针向下移动，直到所有的括号操作完成，如果栈为空，那么该表达式的括号是匹配的，否那么括号不匹配。 j=strlen(str); for(i=0;i<j;i+) if(stri='('|stri='')push(s,str); for(i=0;i<j;i+) if(stri=')') if(*s->top='(') pop(s,&t); else s->top=s->top-1; if(stri='') if(*s->top='') pop(s,&t); else s->top=s->top-1; 4你的应用中采用的是顺序的还是链式的存储结构？为什么要选用这种存储结构。 答：我的应用中采用的是顺序的链式存储结构，因为对于栈这种抽象的数据类型，有着“先进后出的特点，这种特性和表达式中括号匹配的过程相符合，因此我采用了这种存储结构。 5源程序的大致的执行过程是怎样的？ 答：先用编译器编写一个.c的文件，然后编译生成.obj的文件，通过连接将目标文件连接生成一个.exe文件，之后运行文件就可以执行了。 六、附录实验参考的资料 ?数据结构第二版? 闫玉宝编著 清华大学出版社思考题a栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。答：在计算机系统中，使用栈的应用有表达式的计算，迷宫以及括号匹配等。使用队列的应用有打印文档，售票系统，解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等b在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？ 答：对于函数的切换，主要是一个压栈的过程，先以一种约定的方式把参数压栈，然后根据函数地址调用函数，函数执行后根据约定的方式出栈取得参数。实 验 报 告课程名称：数据结构班级：实验成绩：实验名称：栈、队列、字符串和数组学号：批阅教师签字：实验编号：实验三姓名：实验日期：2017-12-7指导教师： 组号：实验时间：18:3022:30一、实验目的（1） 理解分治法的思想。（2） 掌握用分治法解决问题二、实验内容（1） 仔细阅读备选实验的题目，选择一个可选多个作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。2 归并排序« 问题描述目前的网上拍卖系统会显示很多待拍卖的物品，通常这些系统具有按照某个关键字对打出的广告进行排序列出的功能，并且能够按照用户输入的某个关键字进行过虑，找到某些特定的物品。« 编程任务 定义一个Advertisement类，该类中至少包含该物品的数量，名称，联系人e-mail，最好有开拍时间及关闭时间，根据用户输入的关键字比方名称，mail，时间等，利用非递归的归并排序对所有的广告进行排序，并列出所有排好序的广告。« 数据输入由文件input.txt提供输入的所有广告信息。程序中由用户输入要排序的关键字。 « 结果输出 程序运行结束时，排好序的广告输出到文件output.txt中，并为每个广告添加序号。输入文件例如输出文件例如input.txtoutput.txtCoat(物品名称)3数量Skirt5Cap7Bag12Title用户输入按照title排序1Bag122Cap73Coat(物品名称)3数量4Skirt5三、实验环境操作系统：Windows 7调试软件名称：Visio Studio2017上机地点：信息楼B405四、问题分析（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。答：归并操作的工作原理如下：1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置3. 比拟两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指4.针到下一位置5. 重复步骤3直到某一指针到达序列尾6. 将另一序列剩下的所有元素直接复制到合并序列尾（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。 时间O(nlogn)空间O(n) 五、问题解决（1） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述.算法设计：void MergeSort(int* data, int n)int step = 1;while(step < n)for(int i = 0; i <= n-step-1; i += 2*step)Merge(data, i, i+step, step, n);/ 将i和i+step这两个有序序列进行合并/ 序列长度为step/ 当i以后的长度小于或者等于step时，退出step *= 2;void Merge(int* data, int a, int b, int length, int n)int right; if(b+length-1 >= n-1) right = n-b; elseright = length;int* temp = new intlength+right;int i = 0,j = 0;while(i<=length-1&&j<=right-1)if(dataa+i <= datab+j)tempi+j = dataa+i; i+; else tempi+j = datab+j; j+;if(j = right)/ a中还有元素，且全都比b中的大,ai还未使memcpy(data+a+i+j, data+a+i,(length-i)*sizeof(int);memcpy(data+a, temp, (i+j)*sizeof(int) ); delete temp;时间复杂度：时空复杂度：如果输入数据本来就是按非降次序排列的，那么根本不会进入while循环，这就是最好情况，计算时间是O(n)。（2） 针对你所选的问题，你认为应该特别注意哪些方面的处理？比方循环何时结束等。答：对于什么时候将i和i+step这两个有序序列进行合并以及当i以后的长度小于或者等于step时退出要注意处理。（3） 你在调试过程中发现了怎样的问题？又做了怎样的改良？在调试过程中，我发现对于相同值的两个物品无法进行排序，这是由于我的算法在设计过程中没有考虑到这种情况，所以在设计标记数组的时候我就设计了能将两个相同值的物品区分开来。六、实验结果总结 本次实验从写归并排序到实现广告类的排序，都是由自己独立完成，有一整晚没有睡觉都在写这个实验，所以对本次实验的实现过程比拟熟悉，而且还增加了对于商品时间的显示和排序。很久没有用C+的我有点儿生疏，刚开始写起来有点慢，但是还是很好得完成了任务，程序中几乎没有任何的BUG。但是通过本次实验我既加深了对于C+的熟悉程度，也了解到了很多关于归并排序的知识，这些知识对于我以后的程序开发会有比拟大的作用，所以我觉得这次实验对我的作用是比拟大的。1.程序运行截图：实 验 报 告课程名称：数据结构班级：实验成绩：实验名称：栈、队列、字符串和数组学号：批阅教师签字：实验编号：实验四姓名：实验日期：2017-12-18指导教师： 组号：实验时间：18:3022:30一、实验目的（1） 熟练掌握动态规划思想及教材中相关经典算法。（2） 掌握用动态规划解题的根本步骤，能够用动态规划解决一些问题。二、实验内容与实验步骤（1） 仔细阅读备选实验的题目，选择一个可选多个作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。（2） 可供选择的题目有以下2个：(i找零钱问题难度系数为3« 问题描述设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值T1,T2,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。假设只用这些硬币面值，找不出钱数j时，记C(i,j)=。 « 编程任务 设计一个动态规划算法，对1jL，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性« 数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数nn<=13，表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。 « 结果输出 程序运行结束时，将计算出的所需最少硬币个数输出到文件output.txt中。输入文件例如输出文件例如input.txtoutput.txt31 2 593三、实验环境操作系统：Windows 7调试软件名称：Visio Studio2017上机地点：信息楼B405四、问题分析分析要解决的问题，给出你的思路，可以借助图表等辅助表达。答：这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题因为收银台的硬币默认是无穷的，但一种改良版本可以考察有限硬币的情况。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。首先，找零钱问题具有最优子结构性质：兑换零钱问题的最优子结构表述：对于任意需要找的钱数j，一个利用Tn中的n个不同面值钱币进行兑换零钱的最正确方案为P(T(1),j)，P(T(2),j),.,P(T(n),j)，即此时的最少钱币个数，那么P(T(2),j),.,P(T(n),j)一定是利用Tn中n个不同的面值钱币对钱数j=j-P(T(1),j)* T(1)进行兑换零钱的最正确方案。其次，找零钱问题具有重叠于问题性质：当n=1时，即只能用一种钱币兑换零钱，钱币的面值为T0，有b)当n>1时，假设j>Tn,即第n种钱币面值比所兑换零钱数小,因此有。当k为时，C(n,j)到达最小值，有P(T(k0),j)=P(T()，j-T()+1假设j=Tn，即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有C(n,j)=C(n,Tn)=1；假设j<Tn，即第n种钱币面值比所兑换零钱数大，因此兑换零钱只需考虑前n-1种钱币即可，故有C(n,j)=C(n-1,j)，且P(T(n-1),j)=0。从以上讨论可知该问题具有重叠子问题性质。根据分析建立正确的递归关系。答： 分析利用你的想法解决该问题可能会有怎样的时空复杂度。答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：五、问题解决（1） 根据对问题的分析，写出解决方法。答：设数组T中存放的是n种钱币递增的不同面值，所要找的钱数为M,M由用户输入；数组Cj表示利用数Tn兑换零钱数为j时所用的最少钱币个数，即最优值；Pij(1<=i<=n)表示按照上述最优值兑换零钱J时用到钱币面值为第i种钱币的个数。（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。#include <iostream>using namespace std;int main()int c ;int a25=0,a10=0,a5=0,a2=0,a1=0;cout<<"请输入要找的零钱:"<<endl;cin>>c;a25=(c/25);a10=(c%25)/10;a5=(c%25)%10/5;a2=(c%25)%10%5/2;a1=(c%25)%10%5%2;cout<<"需要找以下几种零钱:"<<endl;cout<<"25分的"<<a25<<"枚"<<endl;cout<<"10分的"<<a10<<"枚"<<endl;cout<<"5分的"<<a5<<"枚"<<endl;cout<<"2分的"<<a2<<"枚"<<endl;cout<<"1分的"<<a1<<"枚"<<endl;时间复杂度：从上面算法可知，最优值c的计算过程中，最外层为循环for(j=1;j<=M;j+)嵌套着while(k>1&&flag=0)循环，而while(k>1&flag=0)循环中又嵌套着三个并列的for循环。因此本算法最坏情况下的复杂度是O(M*)；最好的情况当然是里面for循环的条件不满足而不执行，此时的复杂度为O(M*n)。其中：M表示需要兑换的零钱数，对于M来说，该值一般不是很大，对于钱币来说，M会小于100元，即10 000分；n表示钱币的种类，n值一般不会很大如钱币总的有13种(从1分，2分，100元)。经过以上分析，如是最坏情况时的复杂度应为O(M*),那么该值对于内存和运行速度较小的自动售货机等的应用前景那么不会很好。但本算法中的递归结构在M>Tn时，有。可见对于钱币j=M时，求c(n,j)时，并不要求对从1i