2019春第十一周作业
| 这个作业属于哪个课程 | C语言程序设计Ⅱ |
|---|---|
| 这个作业要求在哪里 | 第十一周作业 |
| 我在这个课程的目标是 | 能够使用c语言实现基本的程序设计，以至最后能够设计出较大的项目 |
| 这个作业在哪个具体方面帮助我实现目标 | 学习递归程序设计，宏的基本定义以及文件包含等内容 |
| 参考文献 | C语言程序设计(第3版）； C Primer Plus （第6版） |
一、本周完成的作业
第一部分. 选择题
第二部分.编程题
题目1. 7-1 汉诺塔问题* (10 分)
汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。
请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。
输入格式
圆盘数 起始柱 目的柱 过度柱
输出格式
移动汉诺塔的步骤
每行显示一步操作，具体格式为：
盘片号: 起始柱 -> 目的柱
其中盘片号从 1 开始由小到大顺序编号。
输入样例
3
a c b
输出样例
1: a -> c
2: a -> b
1: c -> b
3: a -> c
1: b -> a
2: b -> c
1: a -> c
1）、实验代码
#include<stdio.h>
void hanio (int n, char op1, char op2, char op3);
int main ()
{
int n;
char op1,op2,op3;
char p,q;
scanf ("%d%c",&n,&p);
scanf ("%c%c%c%c%c",&op1,&q,&op2,&q,&op3);
hanio (n,op1,op2,op3);
return 0;
}
void hanio (int n, char op1, char op2, char op3)
{
if (n==1)
printf ("%d: %c -> %c
",n,op1,op2);
else
{
hanio (n-1,op1,op3,op2);
printf ("%d: %c -> %c
",n,op1,op2);
hanio (n-1,op3,op2,op1);
}
}
2）、设计思路
3）、本题调试过程碰到的问题及解决方法
如图，在最开始写的时候，程序中第21行 printf 语句后面输出的是n-1的值，导致结果中所有圆盘编号都小了一，再仔细读了一遍程序后，发现问题，将n-1改为n即可。
4）、运行结果图
题目2. 7-2 估值一亿的AI核心代码 (20 分)
以上图片来自新浪微博。
本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：
无论用户说什么，首先把对方说的话在一行中原样打印出来；
消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；
把原文中所有大写英文字母变成小写，除了 I；
把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词；
把原文中所有独立的 I 和 me 换成 you；
把原文中所有的问号 ? 换成惊叹号 !；
在一行中输出替换后的句子作为 AI 的回答。
输入格式：
输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。
输出格式：
按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。
输入样例：
6
Hello ?
Good to chat with you
can you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know
输出样例：
Hello ?
AI: hello!
Good to chat with you
AI: good to chat with you
can you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know
1）、实验代码
#include<stdio.h>
#include<string.h>
char a[1050];
char b[1050];
int ac(char t)
{
if((t-'a')>=0&&(t-'a')<26||(t-'A')>=0&&(t-'A')<26||(t-'0')>=0&&(t-'0')<=9)
return 1;
return 0;
}
int main()
{
int i,t,n,m;
scanf("%d",&t);
getchar();
while(t--)
{
gets(a);
printf("%s
",a);
memset(b, 0, sizeof b);
n=strlen(a);
printf("AI:");
m=0;
int o=0;
for(i=0;i<n;i++)
{
if(a[i]==' ')
{
o=1;
}
else
{
if(o==1||i==0)
{
b[m++]=' ';
o=0;
}
if((a[i]-'A')<26&&(a[i]-'A')>=0)
{
if(a[i]!='I')
{
b[m++]=a[i]+32;
}
else
{
b[m++]=a[i];
}
}
else if(a[i]=='?')
{
if(b[m-1]!=' ')
{
b[m++]=' ';
}
b[m++]='!';
}
else if(ac(a[i])==1)
{
b[m++]=a[i];
}
else
{
if(b[m-1]!=' ')
{
b[m++]=' ';
}
b[m++]=a[i];
}
}
}
b[m++]=' ';
printf(" ");
for(i=1;i<m-1;i++)
{
if(b[i]==' ')
{
if(ac(b[i+1])==1)
{
printf(" ");
}
else
{
}
}
else if((b[i]-'a')>=0&&(b[i]-'a')<26)
{
if(b[i]=='c'&&b[i-1]==' '&&b[i+1]=='a'&&b[i+2]=='n'&&b[i+3]==' '&&b[i+4]=='y'&&b[i+5]=='o'&&b[i+6]=='u'&&b[i+7]==' ')
{
printf("I can");
i+=6;
}
else if(b[i]=='c'&&b[i-1]==' '&&b[i+1]=='o'&&b[i+2]=='u'&&b[i+3]=='l'&&b[i+4]=='d'&&b[i+5]==' '&&b[i+6]=='y'&&b[i+7]=='o'&&b[i+8]=='u'&&b[i+9]==' ')
{
printf("I could");
i+=8;
}
else if(b[i]=='m'&&b[i-1]==' '&&b[i+1]=='e'&&b[i+2]==' ')
{
printf("you");
i+=1;
}
else
{
printf("%c",b[i]);
}
}
else if(b[i]=='I'&&b[i-1]==' '&&b[i+1]==' ')
{
printf("you");
}
else
{
printf("%c",b[i]);
}
}
printf("
");
}
return 0;
}
2）、设计思路
3）、本题调试过程碰到的问题及解决方法
查的这个答案还算看得懂一点点，其他的要么是用c++，要么是用Java，要么是Python......其实原理就是按照题目要求去实现就行，只是很繁琐，很麻烦。虽然我现在也不是很懂(因为这段代码中还有部分代码看不懂)。除此之外，在这道题的代码中，我认识了一个新函数，以后可能会用上。0.0
memset()函数
memset()的函数，它可以一字节一字节地把整个数组设置为一个指定的值。 memset()函数在mem.h头文件中声明，它把数组的起始地址作为其第一个参数，第二个参数是设置数组每个字节的值，第三个参数是数组的长度(字节数，不是元素个数)。其函数原型为：void memset(void，int，unsigned)；
详情参考：CSDN博客memset()函数
题目3. 7-3 八皇后问题 (20 分)
在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。
现在我们把棋盘扩展到 n × n 的棋盘上摆放 n 个皇后，请问该怎么摆？请编写程序，输入正整数 n，输出全部摆法(棋盘格子空白处显示句点“.”，皇后处显示字母“Q”，每两格之间空一格)。
输入格式
正整数 n (0 ＜ n ≤ 12)
输出格式
若问题有解，则输出全部摆法(两种摆法之间空一行)，否则输出 None。
要求：试探的顺序逐行从左往右的顺序进行，请参看输出样例2。
输入样例1
3
输出样例1
None
输入样例2
6
输出样例2
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .
. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .
. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .
. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .
1）、实验代码
2）、设计思路
没怎么看懂，不会画....
3）、本题调试过程碰到的问题及解决方法
该种解法是通过一个较简单的例子：n个数的全排列，所形成的剪枝函数稍加修改(改成判断这一行，这一列，斜线有没有皇后)，就变成了八皇后问题。
预习作业
请举实例解释以下几个概念：数组指针，指针数组，指针函数，函数指针，二级指针，单向链表。（无实例不给分）
请用自己的理解回答。如果有引用他人的文字，请一定要标出出处（使用Markdown的链接方式）。
数组指针:是一个指针，指向数组的指针。
例如，如果想将二维数组赋给指针，则可以
int b[3][4];
int(*pp)[4]; //定义一个数组指针，指向含4个元素的一维数组
pp = b; //将该二维数组的首地址赋给pp，也就是b[0]或&b[0]，二维数组中pp=b和pp=&b[0]是等价的
pp++; //pp=pp+1，该语句执行过后pp的指向从行b[0][]变为了行b[1][]，pp=&b[1]
指针数组:是一个数组，装着指针的数组。
例如，如要将二维数组赋给一指针数组，可以
int *p[3];
int a[3][4];
for(i=0;i<3;i++)
p[i]=a[i];
来实现，这里int *p[3] 表示一个一维数组内存放着三个指针变量，分别是p[0]、p[1]、p[2]，所以要分别赋值。
详情参考：博客1,博客2。
指针函数:是一个函数，不过返回时，返回值是一个指针(地址)。
例如，int *fun(int x,int y); 就是一个简单的自定义的一个指针函数的声明写法。它的定义可以根据自己的目的去定义。其返回值是一个 int 类型的指针，是一个地址。
详情参考：博客1,博客2
函数指针:指向函数的指针。是一个指针变量，是一个指向函数的指针变量。
例如，int (fun)(int x,int y); 就是一个函数指针的声明格式。函数指针是需要把一个函数的地址赋值给它，有两种写法：fun = &Function；fun = Function; 取地址运算符&不是必需的，因为一个函数标识符就表示了它的地址，如果是函数调用，还必须包含一个圆括号括起来的参数表。可以用x = (fun)(); 的方式调用函数指针。
详情参考：博客1,博客2
二级指针:指向指针的指针。当你想对一个地址做修改的时候，就要用到二级指针。
例如，
void buf ( int **a )
{
( *a) = ( int* )malloc ( sizeof ( int ) );
( **a )= 1;
printf ( "%d",**a );
}
int main( int argc, char *argv[] )
{
int *a;
buf ( &a );
//printf ( "%d",*a );
}
当你要给*a赋值的时候，发现他是一个指针，没有内存空间来存储值，不能直接给他赋值，要给他先创建一个内存空间。当然你可以直接的malloc ()在主函数里。这个就不说了。但是，如果你想要在调用一个函数实现呢?你可以这样想，如果我有一个东西，能接受我的这个指针的地址，这样就可以在调用的函数里面通过他的地址，就可以在调用的函数里面，进行malloc (),而这个能存储地址的就是二级指针。
详情参考：博客。
单向链表:
单向链表链表是链表的一种。
链表是什么？ 链表是一种常见而重要的动态存储分布的数据结构。可以将一条链表想象成环环相扣的结点，就如平常所见到的锁链一样。链表内包含很多结点（当然也可以包含零个结点）。其中每个结点的数据空间一般会包含一个数据结构（用于存放各种类型的数据）以及一个指针，该指针一般称为next，用来指向下一个结点的位置。由于下一个结点也是链表类型，所以next的指针也要定义为链表类型。
链表的结构
例如：
typedef struct LinkList
{
int Element;
LinkList * next;
}LinkList;
就定义了一种链表的结构类型。
详情参考：链表；C语言程序设计(第3版） P285 。
单向链表的组成如下图，
详情参考：单向链表的建立，可参考：C语言程序设计(第3版） P286；博客。
用链表代替数组进行数据的存储与操作有两优点：一、不需要事先定义存储空间大小，可以实时动态分配，内存使用效率高；二、可以方便地插入新元素（结点），是信息库保持排序状态，操作效率高。
学习进度条
| 周/日期 | 这周所花的时间 | 代码行数 | 学到的知识点简介 | 目前比较迷惑的问题 |
|---|---|---|---|---|
| 3/2-3/8 | 三天六小时 | 50 | 1、定义、运用文件指针；2、如何打开、关闭文件3、如何读出指定文件中的数据；4、如何向指定文件中写入数据； | 字符、字符串有什么区别？二者输入、输出有没有很大不同？什么才算字符串？什么算字符？在文件中二者有没有差别？ |
| 3/9-3/15 | 四天三小时 | 180 | 1、运用二维数组解决问题，矩阵的判断；2、对一组数的所有子数组求和 | 如何在输出时利用数组的性质 |
| 3/16-3/22 | 三天八小时 | 210 | 1、二维数组加深理解，二维数组与矩阵；2、选择排序法解决问题；3、二分查找法 | 二分查找法这周没练习，只是看看书上例题大致懂了，不知道真正应用时能否掌握。 |
| 3/23-3/29 | 三天两小时 | 120 | 1、判断回；文2、字符数组的概念及其简单运用；3、一些简单的与字符数组相关的暂时没接触补充知识，一些函数，用法等。 | 在作业运用文件指针时，一开始总是出现从文件里输不出来结果，打印不出来，后来发现可能与自己输入时格式未搞好，本来不应该出现的空格出现了，导致打印不出来结果。文件指针还不是很熟练 |
| 3/30-4/5 | 两天 | 150 | 1、指针的含义，变量、地址、指针变量等间的关系；2、指针变量的初始化，运用指针做一些简单运算；3、指针与数组之间的关系 | 在用指针处理字符串时，应怎样定义指针变量 |
| 4/6-4/12 | 三天 | 200 | 1、更深一步掌握指针与数组间的关系；2、懂得指针可以实现数组的一些功能；3、指针在碰到字符数组时的应用 | 在代码中，如果遇到要输出单个字符，%s与%c有什么区别？ scanf（）与 getchar 两种输入方式有区别吗？会不会在有些情况下能影响到输出结果？ |
| 4/13-4/19 | 两天 | 170 | 1、学习了与字符串有关的一些字符串处理函数；2、学习了利用指针实现内存动态分配 | 究竟什么情况下采用内存动态分配？具体要采用哪一种动态内存分配？ |
| 4/20-4/26 | 两天 | 135 | 1、学习了结构及结构变量的定义与运用 | 如果运用递归函数解决问题，虽然使代码简化了，更美观了。但会导致相同的运算重复进行，占内存。感觉递归弊大于利。 |
| 4/27-5/3 | 一天 | 1、复习了结构与数组、指针间的关系，两者之间是如何进行替换利用； | ||
| 5/4-5/10 | 三天 | 165 | 1、学习了递归程序的设计；2、宏的基本定义；3、文件包含等内容； | 链表知识点看了看，不是很懂 |
三、学习感悟
本周在做题时，刚看到选择题都懵了。以为是我上课错过了什么，很多题都不确定答案，在翻过书后才发觉，原来是没怎么讲。看过书后有了一点概念。关键还是编程题，哇，感觉编程题难度不小，不，是很大。第一题是在看了例题后，照葫芦画瓢勉强做出来的。后面两道题，看过之后，第一反应是老师是不是出错题目了。之后助教在群里喊话，意思是尽力写，写不出来也要有思路，瞬间就认为自己不需要写出来，写思路就行，但我看了PTA里的提交列表后，发现有不少人都做了出来，有用c++的，有用c的，然后就感觉不能放弃啊，实在不行就搜啊，只要自己看懂了，理解了，记住了，掌握了，也行。最后也勉勉强强理解了第二道编程题，价值一亿的代码。
结对编程感想
结对时，队友选择题答案不确定，互相之间讨论了两下。到编程题时，由于题目较难，队友也不愿直接跳过，两个人上网搜答案，答案看不懂就互相说一说自己的想法，先将答案搞懂。
表格-折线图
| 时间 | 累计代码行数 | 累计博客字数 |
|---|---|---|
| 第一周 | 80 | 275 |
| 第二周 | 50 | 883 |
| 第三周 | 180 | 1303 |
| 第四周 | 210 | 1849 |
| 第五周 | 120 | 1988 |
| 第六周 | 150 | 2717 |
| 第七周 | 200 | 3000 |
| 第八周 | 170 | 2820 |
| 第九周 | 135 | 2855 |
| 第十周 | 3945 | |
| 第十一周 | 165 | 4934 |
