第九周编程总结
| 這個作業屬于那個課程 | C語言程序設計II |
| 這個作業要求在哪里 | https://edu.cnblogs.com/campus/zswxy/MS/homework/3129 |
| 我在這個課程的目標是 | 學好C語言 |
| 這個作業在那個具體方面幫助我實現目標 | 學到了結構體的運用 |
| 參考文獻 | c primer plus |
6-1 按等級統計學生成績 (20 分)
本題要求實現一個根據學生成績設置其等級，并統計不及格人數的簡單函數。
函數接口定義：
int set_grade( struct student *p, int n );
其中p是指向學生信息的結構體數組的指針，該結構體的定義為：
struct student{
int num;
char name[20];
int score;
char grade;
};
n是數組元素個數。學號num、姓名name和成績score均是已經存儲好的。set_grade函數需要根據學生的成績score設置其等級grade。等級設置：85－100為A，70－84為B，60－69為C，0－59為D。同時，set_grade還需要返回不及格的人數。
裁判測試程序樣例：
include <stdio.h>
define MAXN 10
struct student{
int num;
char name[20];
int score;
char grade;
};
int set_grade( struct student *p, int n );
int main()
{ struct student stu[MAXN], *ptr;
int n, i, count;
count = set_grade(ptr, n);
printf("The count for failed (<60): %d\n", count);
printf("The grades:\n");
for(i = 0; i < n; i++)
printf("%d %s %c\n", stu[i].num, stu[i].name, stu[i].grade);
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
10
31001 annie 85
31002 bonny 75
31003 carol 70
31004 dan 84
31005 susan 90
31006 paul 69
31007 pam 60
31008 apple 50
31009 nancy 100
31010 bob 78
輸出樣例：
The count for failed (<60): 1
The grades:
31001 annie A
31002 bonny B
31003 carol B
31004 dan B
31005 susan A
31006 paul C
31007 pam C
31008 apple D
31009 nancy A
31010 bob B
1）實驗代碼
int set_grade( struct student *p, int n ) {int i,count=0;for(i=0;i<n;i++){if((*p).score<=59){(*p).grade = 'D';count++;}else if((*p).score>=60&&(*p).score<=69){(*p).grade = 'C';}else if((*p).score>=70&&(*p).score<=84){(*p).grade = 'B';}else{(*p).grade = 'A';}p++;}return count; }2)設計思路
3）本次調試過程中遇到的問題
問題：if語句中的條件錯誤，還有輸出也錯誤。把if語句改成加等于號的條件，把輸出改為（*p）.grade=' '.并滿足他們的等級條件。
4）運行結果截圖
7-1 一幫一 (15 分)
“一幫一學習小組”是中小學中常見的學習組織方式，老師把學習成績靠前的學生跟學習成績靠后的學生排在一組。本題就請你編寫程序幫助老師自動完成這個分配工作，即在得到全班學生的排名后，在當前尚未分組的學生中，將名次最靠前的學生與名次最靠后的異性學生分為一組。
輸入格式：
輸入第一行給出正偶數N（≤50），即全班學生的人數。此后N行，按照名次從高到低的順序給出每個學生的性別（0代表女生，1代表男生）和姓名（不超過8個英文字母的非空字符串），其間以1個空格分隔。這里保證本班男女比例是1:1，并且沒有并列名次。
輸出格式：
每行輸出一組兩個學生的姓名，其間以1個空格分隔。名次高的學生在前，名次低的學生在后。小組的輸出順序按照前面學生的名次從高到低排列。
輸入樣例：
8
0 Amy
1 Tom
1 Bill
0 Cindy
0 Maya
1 John
1 Jack
0 Linda
輸出樣例：
Amy Jack
Tom Linda
Bill Maya
Cindy John
1）實驗代碼
#include<stdio.h> struct students {int gender;char name[9];int flag; }; int main(){struct students student [50];int i,n,j;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d %s",&student[i].gender,student[i].name);}student[i].flag=0;for(i=0;i<n/2;i++){for(j=n-1;j>=i;j--){if(student[i].gender!=student[j].gender&&student[j].gender!=2){printf("%s %s\n",student[i].name,student[j].name);student[i].flag=1;student[j].gender=2;break;}}}return 0; }2）設計思路
3）調試過程中遇到的問題
問題：if語句少寫了判斷兩者的性別，以及忘了標記已經組隊了的。if語句中加上student[j].gender!=2,再標記student[j].gender=2.
4)運行結果截圖
7-2 考試座位號 (15 分)
每個 PAT 考生在參加考試時都會被分配兩個座位號，一個是試機座位，一個是考試座位。正常情況下，考生在入場時先得到試機座位號碼，入座進入試機狀態后，系統會顯示該考生的考試座位號碼，考試時考生需要換到考試座位就座。但有些考生遲到了，試機已經結束，他們只能拿著領到的試機座位號碼求助于你，從后臺查出他們的考試座位號碼。
輸入格式：
輸入第一行給出一個正整數 N（≤1000），隨后 N 行，每行給出一個考生的信息：準考證號 試機座位號 考試座位號。其中準考證號由 16 位數字組成，座位從 1 到 N 編號。輸入保證每個人的準考證號都不同，并且任何時候都不會把兩個人分配到同一個座位上。
考生信息之后，給出一個正整數 M（≤N），隨后一行中給出 M 個待查詢的試機座位號碼，以空格分隔。
輸出格式：
對應每個需要查詢的試機座位號碼，在一行中輸出對應考生的準考證號和考試座位號碼，中間用 1 個空格分隔。
輸入樣例：
4
3310120150912233 2 4
3310120150912119 4 1
3310120150912126 1 3
3310120150912002 3 2
2
3 4
輸出樣例：
3310120150912002 2
3310120150912119 1
1）實驗代碼
#include<stdio.h> struct student{long int num;int a;int b; }; int main() {int n,m,i,j,c;struct student stu[1000];scanf("%d", &n);for(i = 0; i < n; i++){scanf("%lld %d %d", &stu[i].num, &stu[i].a, &stu[i].b);}scanf("%d",&m);for(j = 0; j < m; j++){scanf("%d",&c);for(i = 0; i< n; i++){if(c == stu[i].a){printf("%lld %d\n", stu[i].num, stu[i].b);break;}}}return 0; }2)設計思路
3）調試過程中遇到的問題
問題：定義變量和輸入寫錯了；把int num改為long int num；第十二行的輸入把&m的條件全刪除，在13行下加上一個scanf("%d",&m);在14行下加入scanf("%d",&c);以及把第18行的代碼刪除。
4）運行結果截圖
請大家查閱資料，思考問題中的三問：什么是遞歸函數，它的優點和缺點有哪些，如何歸納出遞歸式？
遞歸函數是一類從自然數到自然數的函數。優點：代碼簡潔，能夠剪短代碼的行數，使復雜的算法變的簡單。缺點：很容易出錯，使處理器超載運行，以及占用大量內存。
遞歸式：http://blog.csdn.net/a130098300/article/details/7632227
（一）代換法：
實質上就是數學歸納法，先對一個小的值做假設，然后推測更大的值得正確性。由于是數學歸納法，那么我們就需要對值進行猜測?，F在，我們看下面這個例子：
我們先假設一個結論T(n) = O(lg(n - b))，并且假設對T(n / 2上取整)成立（這就是數學歸納法了），那么把T(n / 2上取整)用假設的結論進行代換，我們有T(n) <= lg((n - b)) / 2上取整)
<= lg((n - b) / 2 + 1) + 1 = lg(n - b + 2),對于任意的b >= 2，即滿足要求T(n) <= lg(n) = O(lgn)。證畢。
這是一個很簡單的例子，但是其中有些事情還是要交代的。
一個是結論的猜測不是一個容易的事情。另一個是在上面的例子中我沒有直接下結論說T(n) = O(lg(n))，而是減去了一個常數b，這是為什么呢？答案是：we can prove something stronger for a given value by assuming something stronger for smaller values.還有一點值得說明，請看下面這個例子：
這里出現了sqrt(n)，我們采用變量代換的方法：令n = 2 ^ m,則上式變為T(2 ^ m) = 2T(2 ^ (m / 2) ),再設S(m) = T(2 ^ m)，則得到S(m) = 2S(m / 2) + 1。我們先假設S(m) = m - b <= O(m)，且對S(m / 2)成立，那么S(m) = 2 * (m - b) / 2 + 1 = m - b + 1，對于任意的b >= 1都有S(m) = O(m)，然后回代有T(n) = T( 2 ^ m) = S(m) = O(m) = O(lgn)。
這里我們采用了變量代換的方法。如果假設時，感覺變量不明朗，那么這是一種很有效的方法。
（二）遞歸樹方法：
利用遞歸樹方法求算法復雜度我想最好的例子就是歸并排序了，這里我不想拿歸并排序做例子，而只是用書中一些更簡單形象的例子來說明：
根據上式我們建立遞歸式T(n) = 3T(n / 4) + cn^2，這里我們拋去上下界函數的影響（sloppiness that we can tolerate），并且把Theta(n ^ 2)用cn^2代替。下面建立遞歸樹模型：
在遞歸樹中，每一個結點都代表一個子代價，每層的代價是該層所有子代價的總和，總問題的代價就是所有層的代價總和。
所以，我們利用遞歸樹求解代價，需要知道什么呢，一個是每一層的代價，一個是層數，就是這兩個。
這些，都需要我們用覺察的態度來發現，而事實證明，這不是一件難事，很多情況下是有規律可循的。
我們且看上面這個例子，遞歸樹的構造很簡單，當遞歸調用到邊界是，就達到了常量T(1)，達到常量T(1)所用到的遞歸次數就是整個遞歸樹的深度，我們從圖中可以得到第i層的結點的代價為n / ( 4 ^ i )，當n / (4 ^ i) = 1即i = log4(n)時，遞歸到達了邊界，所以，整個遞歸樹的深度就是i = log4(n)。我們要求的總的代價是所有的總和，結果為O(n ^ 2)。計算過程我就不再累述了。但是，遞歸樹并不是都是這樣的滿的樹，也就是不是每一層的結點都是相同的結構，所以我們在構造遞歸樹的時候要仔細看好這一點，才能保證在計算時不會出錯。
（三）主方法：
其實應該叫做主定理方法，利用這個方法，我們只需要記住主定理的三種情況，并且在滿足一定的條件下，就可以速度解出遞歸式。主定理的三種情況不在這里給出，一定條件我只說一下我對于多項式大于(或小于)的理解，比如x和1.1x，那么x就是多項式小于1.1x，二者差了一個多項式(0.1x)，而至于x與xlgx就不存在多項式大于（或小于）的關系。
學習感悟：
在這周編程中我感覺還好，可能是題目不算太難的結果吧，所以做的很輕松，不過在編程題最后一題中我的變量和輸入語句還是有點錯誤，所以我還是有很多知識點記得的不是很清楚，還是要努力的學習。
結對編程的過程及優缺點：
這周因為編程題不難，所以我們在星期三晚自習的結對編程中就把題目差不多寫完了，我們在自習室中坐在一塊，一起交流自己從這道題中看到的問題以及自己的思路。
優點：能夠更快的理解這道題的要求，以及可以學到很多自己沒想到的思路。
缺點：在一起交流的時間不夠。
轉載于:https://www.cnblogs.com/tzmad/p/10774528.html
總結
