c++編程入門第一次課

一、編程思想和語言基礎(chǔ)王振昊緒論為什么要學(xué)習(xí)編程Oier的尷尬地位怎樣學(xué)好編程課表時(shí)間段安排2月1號2月2號2月3號2月4號2月5號上午講解（8：30-10：30）了解學(xué)生需求

語言：（含結(jié)構(gòu)體與

基本語言技巧）暴力（含BFS、DFS）動態(tài)規(guī)劃及相關(guān)應(yīng)用語言貪心二分（以例題和較深的講解為主）Dp的講解

數(shù)學(xué)（擴(kuò)歐、唯一分解，二項(xiàng)式定理、快速冪）練習(xí)（10：30-11：30）語言題、答疑暴力題目、答疑動態(tài)規(guī)劃習(xí)題、答疑語言題+貪心+二分?jǐn)?shù)學(xué)+Dp習(xí)題下午講解（14：30-17：00）遞歸二分貪心圖論（并查集、生成樹、最短路）遞歸與遞推

Dp的一些講解圖論的理解練習(xí)（6：00-8：00）語言題、遞歸習(xí)題、答疑二分、貪心簡單習(xí)題圖論習(xí)題、答疑語言題+貪心+二分Dp的簡單習(xí)題圖論習(xí)題（較基礎(chǔ)）王振昊薛鑫磊一、編程思想和語言基礎(chǔ)1.1編程思想1.2Ｃ／Ｃ＋＋語言初步1.3結(jié)構(gòu)體（記錄類型）1.4高精度計(jì)算1.1編程思想

程序（program）是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語言編寫的命令序列的集合。為進(jìn)行某活動或過程所規(guī)定的途徑。編程就是讓計(jì)算機(jī)為解決某個(gè)問題而使用某種程序設(shè)計(jì)語言編寫程序代碼，并最終得到結(jié)果的過程。為了使計(jì)算機(jī)能夠理解人的意圖，人類就必須要將需解決的問題的思路、方法、和手段通過計(jì)算機(jī)能夠理解的形式告訴計(jì)算機(jī)，使得計(jì)算機(jī)能夠根據(jù)人的指令一步一步去工作，完成某種特定的任務(wù)。這種人和計(jì)算機(jī)之間交流的過程就是編程。因此，一個(gè)好的程序員必須學(xué)會從計(jì)算機(jī)的角度去思考問題1.1編程思想舉幾個(gè)例子：Swap冒泡排序和插入排序輾轉(zhuǎn)相除法計(jì)算幾何1.1編程思想著名計(jì)算機(jī)科學(xué)家沃思提出一個(gè)公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序。實(shí)際上，一個(gè)程序除了以上兩個(gè)主要的要素外，還應(yīng)當(dāng)采用程序設(shè)計(jì)方法進(jìn)行設(shè)計(jì)，并且用一種計(jì)算機(jī)語言來表示。因此，算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語言工具4個(gè)方面是一個(gè)程序員所應(yīng)具備的知識。1.1編程思想推薦幾本經(jīng)典的書1.2Ｃ／Ｃ＋＋語言初步C語言是一種計(jì)算機(jī)程序設(shè)計(jì)語言，它既具有高級語言的特點(diǎn)，又具有匯編語言的特點(diǎn)。隨著微型計(jì)算機(jī)的日益普及,出現(xiàn)了許多C語言版本。由于沒有統(tǒng)一的標(biāo)準(zhǔn),使得這些C語言之間出現(xiàn)了一些不一致的地方。為了改變這種情況,美國國家標(biāo)準(zhǔn)研究所(ANSI)為C語言制定了一套ANSI標(biāo)準(zhǔn)，成為現(xiàn)行的C語言標(biāo)準(zhǔn)。C語言是世界上最流行、使用最廣泛的高級程序設(shè)計(jì)語言之一。1.2Ｃ／Ｃ＋＋語言初步先從簡單的入手： A+BProblem:

輸入格式:

兩個(gè)自然數(shù)a和b(0<=a,b<=32767)

輸出格式:

一個(gè)數(shù)，即a和b的和1.2Ｃ／Ｃ＋＋語言初步程序：#include<stdio.h>;intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d",a+b);}1.2Ｃ／Ｃ＋＋語言初步用程序使計(jì)算機(jī)按照題目描述過程得出結(jié)果稱為模擬NOIP中第一道題往往是模擬題，也是常說的送分題，要做對這樣的題，要求熟練掌握編程語言和簡單基本的算法簡單基本算法主要指：排序、求最大（最?。┲档认旅婵吹篮唵蔚哪M題明明的隨機(jī)數(shù)題目描述：明明想在學(xué)校中請一些同學(xué)一起做一項(xiàng)問卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了N個(gè)1到1000之間的隨機(jī)整數(shù)（N≤100），對于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作。輸入格式：輸入有2行，第1行為1個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)：N第2行有N個(gè)用空格隔開的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。輸出格式：輸出也是2行，第1行為1個(gè)正整數(shù)M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第2行為M個(gè)用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。明明的隨機(jī)數(shù)本題的幾種思路快速排序？冒泡排序？注意題目數(shù)據(jù)大小桶排序明明的隨機(jī)數(shù)#include<stdio.h>intmain(){intser_num[1001]={0};intn,m=0,t,i,j;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&t);ser_num[t]++;//計(jì)一個(gè)數(shù)出現(xiàn)的次數(shù)}明明的隨機(jī)數(shù) for(i=0;i<=1000;i++) for(j=1;j<=ser_num[i];j++) if(ser_num[i]>1) m++; printf("%d\n",n); for(i=0;i<=1000;i++) for(j=1;j<=ser_num[i];j++) if(ser_num[i]>1) printf("%d",i); printf(“\n”); return0;}1.2Ｃ／Ｃ＋＋語言初步C++是一種面向?qū)ο蟮挠?jì)算機(jī)程序設(shè)計(jì)語言。它是一種使用非常廣泛的計(jì)算機(jī)編程語言。C++是一種靜態(tài)數(shù)據(jù)類型檢查的、支持多重編程范式的通用程序設(shè)計(jì)語言。它支持過程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。參考書籍：C++Primer1.3結(jié)構(gòu)體（記錄類型）結(jié)構(gòu)體（struct），也叫結(jié)構(gòu)，是由一系列具有相同類型或不同類型的數(shù)據(jù)構(gòu)成的數(shù)據(jù)集合。

1.結(jié)構(gòu)說明和結(jié)構(gòu)變量定義

在TurboC中,結(jié)構(gòu)也是一種數(shù)據(jù)類型,可以使用結(jié)構(gòu)變量,因此,

象其它

類型的變量一樣,在使用結(jié)構(gòu)變量時(shí)要先對其定義。

定義結(jié)構(gòu)變量的一般格式為:

struct結(jié)構(gòu)名

{

類型

變量名;

類型

變量名;

...

}結(jié)構(gòu)變量;

結(jié)構(gòu)名是結(jié)構(gòu)的標(biāo)識符不是變量名。

1.3結(jié)構(gòu)體（記錄類型）

下面舉一個(gè)例子來說明怎樣定義結(jié)構(gòu)變量。

structstring

{

charname[8];

intage;

charsex[2];

chardepart[20];

floatwage1,wage2,wage3,wage4,wage5;

}person;

1.3結(jié)構(gòu)體（記錄類型）其實(shí)沒有什么題是必須用結(jié)構(gòu)體來做的（除了用指針構(gòu)建鏈表時(shí)），多用幾個(gè)變量可以達(dá)到同樣的效果。但用結(jié)構(gòu)體可以增強(qiáng)代碼的完整性和可懂性。下面看道例題：

誰拿了最多獎學(xué)金

題目描述某校的慣例是在每學(xué)期的期末考試之后發(fā)放獎學(xué)金。發(fā)放的獎學(xué)金共有五種，獲取的條件各自不同：

1)院士獎學(xué)金，每人8000元，期末平均成績高于80分（>80），并且在本學(xué)期內(nèi)發(fā)表1篇或1篇以上論文的學(xué)生均可獲得；

2)五四獎學(xué)金，每人4000元，期末平均成績高于85分（>85），并且班級評議成績高于80分（>80）的學(xué)生均可獲得；

3)成績優(yōu)秀獎，每人2000元，期末平均成績高于90分（>90）的學(xué)生均可獲得；

4)西部獎學(xué)金，每人1000元，期末平均成績高于85分（>85）的西部省份學(xué)生均可獲得；

5)班級貢獻(xiàn)獎，每人850元，班級評議成績高于80分（>80）的學(xué)生干部均可獲得；只要符合條件就可以得獎，每項(xiàng)獎學(xué)金的獲獎人數(shù)沒有限制，每名學(xué)生也可以同時(shí)獲得多項(xiàng)獎學(xué)金。例如姚林的期末平均成績是87分，班級評議成績82分，同時(shí)他還是一位學(xué)生干部，那么他可以同時(shí)獲得五四獎學(xué)金和班級貢獻(xiàn)獎，獎金總數(shù)是4850元?，F(xiàn)在給出若干學(xué)生的相關(guān)數(shù)據(jù)，請計(jì)算哪些同學(xué)獲得的獎金總數(shù)最高（假設(shè)總有同學(xué)能滿足獲得獎學(xué)金的條件）。

誰拿了最多獎學(xué)金輸入格式輸入的第一行是一個(gè)整數(shù)N（1<=N<=100），表示學(xué)生的總數(shù)。接下來的N行每行是一位學(xué)生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學(xué)生干部，是否是西部省份學(xué)生，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成績都是0到100之間的整數(shù)（包括0和100）；是否是學(xué)生干部和是否是西部省份學(xué)生分別用一個(gè)字符表示，Y表示是，N表示不是；發(fā)表的論文數(shù)是0到10的整數(shù)（包括0和10）。每兩個(gè)相鄰數(shù)據(jù)項(xiàng)之間用一個(gè)空格分隔。輸出格式輸出包括三行，第一行是獲得最多獎金的學(xué)生的姓名，第二行是這名學(xué)生獲得的獎金總數(shù)。如果有兩位或兩位以上的學(xué)生獲得的獎金最多，輸出他們之中在輸入文件中出現(xiàn)最早的學(xué)生的姓名。第三行是這N個(gè)學(xué)生獲得的獎學(xué)金的總數(shù)。

誰拿了最多獎學(xué)金#include<cstdio>intmain(){charname[101][30],ganbu[101][5],xibu[101][5];intqimo[101],banji[101],wen[101],money[101]={0};intn,i,j=0,k,l=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%s%d%d%s%s%d",&name[i],&qimo[i],&banji[i],&ganbu[i],&xibu[i],&wen[i]);if(qimo[i]>80&&wen[i]>=1)money[i]+=8000;if(qimo[i]>85&&banji[i]>80)money[i]+=4000;if(qimo[i]>90)money[i]+=2000;if(qimo[i]>85&&xibu[i][0]=='Y')money[i]+=1000;if(banji[i]>80&&ganbu[i][0]=='Y')money[i]+=850;if(money[i]>j){j=money[i];k=i;}l+=money[i];}printf("%s\n%d\n%d\n",name[k],money[k],l);return0;}1.4高精度計(jì)算利用計(jì)算機(jī)進(jìn)行數(shù)值計(jì)算，有時(shí)會遇到這樣的問題：有些計(jì)算要求精度高，希望計(jì)算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計(jì)算機(jī)的計(jì)算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實(shí)際問題所要求的精度。我們可以利用程序設(shè)計(jì)的方法去實(shí)現(xiàn)這樣的高精度計(jì)算。介紹常用的幾種高精度計(jì)算的方法。 高精度計(jì)算中需要處理好以下幾個(gè)問題： (1)數(shù)據(jù)的接收方法和存貯方法 數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長時(shí)，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。 voidinit(inta[])//傳入一個(gè)數(shù)組 {strings; cin>>s;//讀入字符串s a[0]=s.length();//用a[0]計(jì)算字符串s的位數(shù) for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲 }另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。1.4高精度計(jì)算2)高精度數(shù)位數(shù)的確定位數(shù)的確定：接收時(shí)往往是用字符串的，所以它的位數(shù)就等于字符串的長度。(3)進(jìn)位,借位處理加法進(jìn)位：c[i]=a[i]+b[i];if(c[i]>=10){c[i]%=10;++c[i+1];}減法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}c[i]=a[i]-b[i];乘法進(jìn)位：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;(4)商和余數(shù)的求法商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理.【例1】高精度加法。輸入兩個(gè)正整數(shù)，求它們的和?！痉治觥枯斎雰蓚€(gè)數(shù)到兩個(gè)變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C++語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個(gè)被加數(shù)很大時(shí)，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時(shí)，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個(gè)整數(shù)相加的算法。856+2551111

圖1A3A2A1+B3B2B1

C4C3C2C1

圖2

如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)組C存儲結(jié)果。則上例有A[1]=6，A[2]=5，A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1，C[3]=1，C[2]=1，C[1]=1，兩數(shù)相加如圖2所示。因此，算法描述如下：intc[100];voidadd(inta[],intb[])//a,b,c都為數(shù)組，分別存儲被加數(shù)、加數(shù)、結(jié)果{inti=1,x=0;//x是進(jìn)位while((i<=a數(shù)組長度)||(i<=b數(shù)組的長度)){c[i]=a[i]+b[i]+x; //第i位相加并加上次的進(jìn)位x=c[i]/10; //向高位進(jìn)位c[i]%=10;//存儲第i位的值i++;//位置下標(biāo)變量}}

通常，讀入的兩個(gè)整數(shù)用可用字符串來存儲，程序設(shè)計(jì)如下：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){ chara1[100],b1[100]; inta[100],b[100],c[100],lena,lenb,lenc,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); gets(a1); gets(b1); //輸入加數(shù)與被加數(shù) lena=strlen(a1); lenb=strlen(b1); for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48; //加數(shù)放入a數(shù)組 for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;//加數(shù)放入b數(shù)組 lenc=1; x=0;

while(lenc<=lena||lenc<=lenb) { c[lenc]=a[lenc]+b[lenc]+x;//兩數(shù)相加 x=c[lenc]/10; c[lenc]%=10; lenc++; } c[lenc]=x; if(c[lenc]==0) lenc--;//處理最高進(jìn)位 for(i=lenc;i>=1;i--) cout<<c[i];//輸出結(jié)果 cout<<endl; return0;}【例2】高精度減法。輸入兩個(gè)正整數(shù)，求它們的差。【算法分析】類似加法，可以用豎式求減法。在做減法運(yùn)算時(shí)，需要注意的是：被減數(shù)必須比減數(shù)大，同時(shí)需要處理借位。高精度減法的參考程序：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){ inta[256],b[256],c[256],lena,lenb,lenc,i; charn[256],n1[256],n2[256]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c));

printf("Inputminuend:");gets(n1);//輸入被減數(shù) printf("Inputsubtrahend:");gets(n2);//輸入減數(shù) if(strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))//strcmp()為字符串比較函數(shù)，當(dāng)n1==n2,返回0;//n1>n2時(shí)，返回正整數(shù)；n1<n2時(shí)，返回負(fù)整數(shù) {//處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù) strcpy(n,n1);//將n1數(shù)組的值完全賦值給n數(shù)組 strcpy(n1,n2); strcpy(n2,n); cout<<"-";//交換了減數(shù)和被減數(shù)，結(jié)果為負(fù)數(shù) }

lena=strlen(n1);lenb=strlen(n2); for(i=0;i<=lena-1;i++)a[lena-i]=int(n1[i]-'0');//被減數(shù)放入a數(shù)組 for(i=0;i<=lenb-1;i++)b[lenb-i]=int(n2[i]-'0');//減數(shù)放入b數(shù)組

i=1; while(i<=lena||i<=lenb) { if(a[i]<b[i]) { a[i]+=10;//不夠減，那么向高位借1當(dāng)10 a[i+1]--; } c[i]=a[i]-b[i];//對應(yīng)位相減 i++; } lenc=i; while((c[lenc]==0)&&(lenc>1))lenc--;//最高位的0不輸出 for(i=lenc;i>=1;i--)cout<<c[i];//輸出結(jié)果 cout<<endl; return0;}【例3】高精度乘法。輸入兩個(gè)正整數(shù)，求它們的積。【算法分析】

類似加法，可以用豎式求乘法。在做乘法運(yùn)算時(shí)，同樣也有進(jìn)位，同時(shí)對每一位進(jìn)行乘法運(yùn)算時(shí)，必須進(jìn)行錯位相加，如圖3、圖4。分析c數(shù)組下標(biāo)的變化規(guī)律，可以寫出如下關(guān)系式：ci=c’i+c”i+…由此可見，ci跟a[i]*b[j]乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原ci的值有關(guān)，分析下標(biāo)規(guī)律，有c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;856×254280171221400

圖3A3A2A1

×B2B1

C’4C’3C’2C’1

C”5C”4C”3C”2

C6C5C4C3C2C1圖4高精度乘法的參考程序：#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){chara1[100],b1[100];inta[100],b[100],c[100],lena,lenb,lenc,i,j,x;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));gets(a1);gets(b1);lena=strlen(a1);lenb=strlen(b1);for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;

for(i=1;i<=lena;i++) { x=0;//用于存放進(jìn)位 for(j=1;j<=lenb;j++)//對乘數(shù)的每一位進(jìn)行處理 { c[i+j-1]=a[i]*b[j]+x+c[i+j-1];//當(dāng)前乘積+上次乘積進(jìn)位+原數(shù) x=c[i+j-1]/10; c[i+j-1]%=10; } c[i+lenb]=x;//進(jìn)位 } lenc=lena+lenb; while(c[lenc]==0&&lenc>1)//刪除前導(dǎo)0 lenc--; for(i=lenc;i>=1;i--) cout<<c[i]; cout<<endl; return0;}【例4】高精度除法。輸入兩個(gè)正整數(shù)，求它們的商（做整除）?！舅惴ǚ治觥?/p>

做除法時(shí)，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時(shí)，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。當(dāng)然，為了程序簡潔，可以避免高精度除法，用0～9次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法。#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){ chara1[100],c1[100]; inta[100],c[100],lena,i,x=0,lenc,b; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); gets(a1); cin>>b; lena=strlen(a1); for(i=0;i<=lena-1;i++) a[i+1]=a1[i]-48;

for(i=1;i<=lena;i++)//按位相除 { c[i]=(x*10+a[i])/b; x=(x*10+a[i])%b; } lenc=1; while(c[lenc]==0&&lenc<lena) lenc++;//刪除前導(dǎo)0 for(i=lenc;i<=lena;i++) cout<<c[i]; cout<<endl; return0;}

實(shí)質(zhì)上，在做兩個(gè)高精度數(shù)運(yùn)算時(shí)候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個(gè)數(shù)字，而采取保留多位數(shù)（例如一個(gè)整型或長整型數(shù)據(jù)等），這樣，在做運(yùn)算（特別是乘法運(yùn)算）時(shí)，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運(yùn)算，其他運(yùn)算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成。示例：123456789÷45=1’2345’6789÷45=274’3484∵1/45=0，1%45=1∴取12345/45=274∵12345%45=15∴取156789/45=3484∴答案為2743484,余數(shù)為156789%45=9圖5

【例5】高精除以高精，求它們的商和余數(shù)。 【算法分析】 高精除以低精是對被除數(shù)的每一位（這里的“一位”包含前面的余數(shù)，以下都是如此）都除以除數(shù)，而高精除以高精則是用減法模擬除法，對被除數(shù)的每一位都減去除數(shù)，一直減到當(dāng)前位置的數(shù)字（包含前面的余數(shù)）小于除數(shù)（由于每一位的數(shù)字小于10，所以對于每一位最多進(jìn)行10次計(jì)算）具體實(shí)現(xiàn)程序如下：

#include<iostream>#include<cstring>usingnamespacestd;inta[101],b[101],c[101],d,i;voidinit(inta[]){strings; cin>>s;//讀入字符串s a[0]=s.length();//用a[0]計(jì)算字符串s的位數(shù) for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲．}voidprint(inta[])//打印輸出{ if(a[0]==0){cout<<0<<endl;return;} for(inti=a[0];i>0;i--)cout<<a[i]; cout<<endl; return;}

intcompare(inta[],intb[]) //比較a和b的大小關(guān)系，若a>b則為1，a<b則為-1,a=b則為0{ if(a[0]>b[0])return1;//a的位數(shù)大于b則a比b大 if(a[0]<b[0])return-1;//a的位數(shù)小于b則a比b小 for(i=a[0];i>0;i--)//從高位到低位比較 { if(a[i]>b[i])return1; if(a[i]<b[i])return-1; } return0;//各位都相等則兩數(shù)相等。}voidnumcpy(intp[],intq[],intdet)//復(fù)制p數(shù)組到q數(shù)組從det開始的地方{ for(inti=1;i<=p[0];i++)q[i+det-1]=p[i]; q[0]=p[0]+det-1;}

voidjian(inta[],intb[])//計(jì)算a=a-b{ intflag,i; flag=compare(a,b);//調(diào)用比較函數(shù)判斷大小 if(flag==0){a[0]=0;return;}//相等 if(flag==1)//大于 { for(i=1;i<=a[0];i++) { if(a[i]<b[i]){a[i+1]--;a[i]+=10;}//若不夠減則向上借一位 a[i]-=b[i]; } while(a[0]>0&&a[a[0]]==0)a[0]--;//修正a的位數(shù) return; }}

voidchugao(inta[],intb[],intc[]){ inttmp[101]; c[0]=a[0]-b[0]+1; for(inti=c[0];i>0;i--) { memset(tmp,0,sizeof(tmp));//數(shù)組清零 numcpy(b,tmp,i); while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}//用減法來模擬 } while(c[0]>0&&c[c[0]]==0)c[0]--; return;}

intmain(){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); init(a);init(b); chugao(a,b,c); print(c); print(a); return0;}

【例6】回文數(shù)【問題描述】 若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個(gè)10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個(gè)回文數(shù)。又如，對于10進(jìn)制數(shù)87，STEPl：87＋78=165STEP2：165＋561=726STEP3：726＋627＝1353STEP4：1353+3531=4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個(gè)程序，給定一個(gè)N（2＜N＜＝10或N=16）進(jìn)制數(shù)M．求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進(jìn)制運(yùn)算1、當(dāng)前位規(guī)范由%10改為%n2、進(jìn)位處理由/10改為/n3、其他運(yùn)算規(guī)則不變

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intn,a[101],b[101],ans,i;voidinit(inta[])//將數(shù)串s轉(zhuǎn)化為整數(shù)數(shù)組a{ strings; cin>>n>>s;//讀入字符串s memset(a,0,sizeof(a));//數(shù)組a清0 a[0]=s.length();//用a[0]計(jì)算字符串s的位數(shù) for(i=1;i<=a[0];i++) if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0'; elsea[i]=s[a[0]-i]-'A'+10;}boolcheck(inta[])//判別整數(shù)數(shù)組a是否為回文數(shù){ for(i=1;i<=a[0];i++) if(a[i]!=a[a[0]-i+1])returnfalse; returntrue;}

voidjia(inta[])//整數(shù)數(shù)組a與其反序數(shù)b進(jìn)行n進(jìn)制加法運(yùn)算{ for(inti=1;i<=a[0];i++)b[i]=a[a[0]-i+1];//反序數(shù)b for(inti=1;i<=a[0];i++)a[i]+=b[i];//逐位相加 for(inti=1;i<=a[0];i++)//處理進(jìn)位 {a[i+1]+=a[i]/n; a[i]%=n; } if(a[a[0]+1]>0)a[0]++;//修正新的a的位數(shù)（a+b最多只能的一個(gè)進(jìn)位）}intmain(){ init(a); if(check(a)){cout<<0<<endl;return0;} ans=0;//步數(shù)初始化為0 while(ans++<=30) {jia(a); if(check(a)){cout<<ans<<endl;return0;} } cout<<"Impossible";//輸出無解信息 return0;}【上機(jī)練習(xí)】1、求N！的值【問題描述】

用高精度方法，求N！的精確值(N以一般整數(shù)輸入)?！据斎霕永縩i.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】

計(jì)算A/B的精確值，設(shè)A，B是以一般整數(shù)輸入，計(jì)算結(jié)果精確小數(shù)后20位。【輸入樣例】ab.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例