第一阶段 面向过程
第一阶段面向过程程序设计
1.编程序用迭代法求a的立方根,求立方根的迭代公式为::Xi+1=(2*Xi)/3+a/(3*Xi*Xi)
假定X的初值为a,迭代到|Xi+1-Xi|<10的-5次方为止. 显示a=3,27的值,并通过调用
pow(a,1.0/3)函数加以验证.。
2. 编程序,从键盘输入正整数n,求出n与其反序数之和并输出。例如,输入2038,输出应为2038+8302=10340。
3编程序,使用如下所谓的简单变量“数据平移”方法来求出Fibonacci数列的第n项(的具体项值)并显示在屏幕上(正整数n通过键盘输入):说明变量old1=1,old2=1,newItem;
新的Fibonacci项newItem总是“距它最近”的前两项(old1与old2)的累加和。而后通过“old1=old2; old2=newItem;”进行所谓的“数据平移”。接着计算另一个新的Fibonacci 项newItem,依次循环,直到求出数列的第n项时为止。
Fibonacci数列的计算公式如下:
fib(1)= 1;
fib(2)= 1;
fib(n)= fib(n-1)+ fib(n-2);//对大于等于3的任意n。
拓展编程(选做),设计递归函数double fib(int n);用于求出Fibonacci数列的第n项(的具体项值)并返回,而后编制主函数对它进行调用。
4.编程序,输入正整数m,它代表一个人民币钱数(元数)。求取这样一个方案,使用最
少张数的人民币纸币,凑成上述的钱数m,并输出求取结果。
注意,现在共有7种元以上面值的人民币纸币,分别为:100,50,20,10,5,2,1。
5.编程序,使用户任意输入一个年份以及该年的1月1日是星期几,而后任意指定某一
天(再输入该年的任意一个月份日期),由程序计算出这一天是星期几。注意,2月份闰年为29天,非闰年为28天;可被4整除而不可被100整除的年份、或者可被400整除的年份均为闰年。
思考:利用元年元月元日(即1年1月1日)是星期一的已知事实,可对程序进行改造,让用户仅输入一个表示日期的年月日,则程序就应计算出那一天是星期几。
拓展编程序(选做),设计星座的计算。
6.编写程序求解骑士巡游问题:在n行n列的棋盘上(如n=5),假设一位骑士(按象棋中
“马走日”的行走法)从初始坐标位置(x1,y1)出发,要遍访(巡游)棋盘中的每一个位置一次。请编一个程序,为骑士求解巡游“路线图”(或告诉骑士,从某位置出发时,无法遍访整个棋盘—问题无解)。
当n=5时,意味着要在5行5列的棋盘的25个“点”处,按骑士行走规则,依次将1至25这25个“棋子”(数码)分别摆放到棋盘上(摆满25个位置则成功,否则失败问题无解)。
例如,当n=5且初始坐标位置定为(1,1) —即最左上角的那个点时,如下是一种巡游“路线图”。程序执行后的输出结果为:
(x1,y1)? => (1=>5, 1=>5) : 1 1
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
提示:
(1)“棋盘”可用二维数组B表示。
(2)编制一个具有如下原型的递归函数solve,用于完成任务:从(i,j)点出发,做第k 至第n*n(即n的平方)次的移动—将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中,若成功则通过引用参数ok返回true,否则返回false。
void solve(int i, int j, int k, bool& ok);
(3)编制主函数,让用户输入作为巡游起点的初始坐标位置(x1,y1),在该处摆放“棋子”(数码)1,而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。
欲处理的初始问题为:从某点(x1,y1)出发,按所给行走规则,作24次移动,遍访棋盘中没被访问过的各点(或发现无路可走)。
可分解化简为如下两个子问题(正是形成递归函数的基础):
①由点(x1,y1)出发,按所给行走规则作1次移动到达(g,h)(或发现无路可走);
②从(g,h)点出发,按所给行走规则,作23次移动,遍访棋盘中没被访问过的各点(或发现无路可走)。
solve函数具体实现时,若由(i,j)点出发已“无路可走”,则将引用参数ok置为false而递归出口;否则,先“迈一步”到达(g,h)点,而后再进行递归调用:solve(g, h, k+1, ok);以实现从新点(g,h)出发,将k+1直到25这些“棋子”(数码)分别摆放到棋盘上,若成功则通过引用参数ok返回true(否则返回false)。
点评:
(1)也可编制第二种解法的主函数:将棋盘上的n平方个点依次作为巡游起点的初始坐标位置(x1,y1),判断从每一位置出发是否有解或无解(输出“OK!”或“NO!”,但并不输出“路线图”)。
(2)若更改程序中的n值(如改为4或6等),便可求解其他阶数的巡游“路线图”。
(3)可改用非递归方法设计并编写solve函数,那样的话,通常要增加一个记录摆放“棋子”信息的数组,可记录下是沿着什么方向到达了当前的什么位置(在那儿摆放了“棋子”)等,而且对上述数组可按照栈(stack)的方式来使用(栈总是采用FILO即所谓的先进后出使用方式),以便在“无路可走”的情况下,回退(回溯)到上一个位置,接着按照另外的方向去寻找其他的“行走”方法。
7.将输入的罗马数据化为10进制数。假设罗马数据中只使用如下7个“基值”字母:M、
D、C、L、X、V、I,分别用来表示1000、500、100、50、10、5、1。如,罗马数据
LXXXVII表示10进制的87。
将输入的10进制正整数转换为罗马数据。假设罗马数据中只使用“基值”字母:M、D、C、L、X、V、I,分别用来表示1000、500、100、50、10、5、1。
8.编程序,循环进行如下的处理过程:由计算机生成简单的四则运算题;用户给出答案;
计算机判断对错。直到用户回答说不再继续做了时结束程序。
提示:可让用户选择指定出加、减、乘、除哪一种运算题,以及出一位数还是两位数的运算题;而后通过使用“rand()%10”或“rand()%100”来获得一个0到9的一位整数随机值或得到0到99的两位整数随机值来为用户出题。还可进一步对用户所做算术题的对错次数进行
记录,结束程序时给出一个某种形式的成绩。
9.编程序,按如下要求来求解任意阶数满秩矩阵的逆矩阵。
(1)矩阵行数(阶数)n之值由用户通过键盘输入;
(2)将欲求逆的“原始矩阵”另加一个“单位矩阵”存放在于数组A之中,而n行2n列的A存储空间通过new来动态分配,且“原始矩阵”的各元素值也由用户通过键盘输入;(3)利用行初等变换设法将A左半的“原始矩阵”化为“单位矩阵”,此时,右半的原“单位矩阵”则变成了欲求的结果逆矩阵。
提示:将整个求解任务(总任务)进行“分解”,设计出多个各负其责的自定义函数以完成各子任务。
求取逆矩阵的主要工作是:利用行初等变换(如将某一行的各数据乘以适当的倍数加到另一行的对应各元素上去),设法将A左半的“原始矩阵”化为“单位矩阵”(首先将“左半”消为“上三角”;又将“左半”主对角线消为1;最后将“左半”消为单位矩阵),此时,右半的原“单位矩阵”则变成了欲求的逆矩阵。
10.编写程序对八皇后问题进行求解:在8行8列的棋盘上放置8个皇后,使任一个皇后都
不能吃掉其他的7个皇后(注:皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子),并将结果以某种方式显示出来。
例如,当求出下述的一个解时,可输出如下信息来表示该解(输出了表示摆放皇后的坐标位置以及“棋盘状态”—棋盘中有皇后的位置放一个“Q”字符,其他位置为“+”字符)。(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
Q + + + + + + +
+ + + + + + Q +
+ + + + Q + + +
+ + + + + + + Q
+ Q + + + + + +
+ + + Q + + + +
+ + + + + Q + +
+ + Q + + + + +
提示:
(1)通过“int LineNum[9]; bool a[9], b[15], c[15];”说明具有全局作用域的4个数组。其中的:
LineNum[i]表示第i列的皇后要放的行位置(只用其中的列号1到8);
a[i]为true(i =1,2,…,8)表示第i行上尚未放皇后;
b[i]为true(i =0,1,2,…,14)表示第i条斜对角线上尚未放皇后(斜对角线指的是“/”状对角线,该对角线上各点的行列号之和i+j为一个常数);
c[i]为true(i=0,1,2,…,14)表示第i条反斜对角线上尚未放皇后(反斜对角线指的是“\”状对角线,该对角线上各点的行列号之差i-j为一个常数)。
从而当使用语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”时,可用于判断并实现:如果在第j行的第i列上放置皇后安全的话,则将一枚皇后放置到那儿。
(2)编制一个具有如下原型的递归函数solve,它负责往第i列开始的连续8-i+1列上均放上皇后,若成功则通过引用参数ok返回true(否则返回false)。
void solve(int i, bool& ok);
摆放皇后之后,若i=8即已放满时则递归出口;否则通过solve(i+1,ok);进行递归调用。
(3)编制主函数,首先初始化一个“空棋盘”,即将a、b、c数组的各元素均置为true (表示当前棋盘的8个行、15条斜对角线以及15条反斜对角线上都尚未摆放皇后)。而后
执行调用语句“solve(1, ok);”,它负责往第1列开始的连续8列上均放上皇后,若成功则通过引用参数ok返回true(否则返回false)。
点评:
(1)可改用非递归方法设计并编写solve函数,那样的话,通常要设置数组来记录皇后的摆放位置信息,还要记录这些皇后所产生的“影响面”(所建立的“势力范围”)—使得哪些行列位置不可再摆放皇后。当在新的行列位置摆放了皇后、但此时又无法进一步摆放其他的皇后时,要回退(回溯)到上一个位置接着去考虑另外的“行走”方法(若还有的话)等等。但注意,“回退”一步后,要同时“撤销”由于该步的回退而关联的那些“影响面”(释放“势力范围”)。
(2)本程序只是找到了某一种“摆放方案”而终止,还可进一步考虑寻找其他各种不同的“摆放方案”(实际上共有92种)。
(3)也可用同样的方法去处理其他“阶数”的皇后问题,如求解四皇后问题等。
第4题:
#include
using namespace std;
int a[8]={0,100,50,20,10,5,2,1}
int main()
{
int n,i,s=0;
cin>>n;
for (i=1;i<=7;i++)
{
s+=n/a[i];
n%=a[i];
}
cout<
return 0;
}
第5题:
#include
using namespace std;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
int i,s=0,year,month,day;
puts("请输入1月1日是星期几");
cin>>n;
puts("请输入要查找的日期");
cin>>year>>month>>day;
if ((year%4==0&&year&100!=0)||year%400==0) a[2]=29;
for (i=1;is%=7;
s+=n;
s%=7;
printf("星期");
switch(s)
{
case 1:
puts("一");
break;
case 2:
puts("二");
break;
case 3:
puts("三");
break;
case 4:
puts("四");
break;
case 5:
puts("五");
break;
case 6:
puts("六");
break;
case 7:
puts("七");
break;
}
return 0;
}
第2题
#include
#include
#include
using namespace std;
int main()
{
string num;
cout<<"请输入一个数:";
cin>>num;
int i=num.size();
int result=0;
int j;
for(j=i-1;j>=0;j--)
{
result+=(num[j]+num[i-1-j]-2*'0')*pow(10,j);
}
cout<return 0;
}
第6题
#include
#include
int map[9][9];//用来标记的二维数组
int n=5;//实际计算时的棋盘大小,超过5时运算时间过长,小于5时无解class Knight{
private:
int dirx[8];//八个方向可以走,用两个数组分别记录每个方向上x,y的坐标位移int diry[8];
public:
Knight(){
dirx[0]=1;diry[0]=2;
dirx[1]=2;diry[1]=1;
dirx[2]=1;diry[2]=-2;
dirx[3]=2;diry[3]=-1;
dirx[4]=-1;diry[4]=2;
dirx[5]=-2;diry[5]=1;
dirx[6]=-1;diry[6]=-2;
dirx[7]=-2;diry[7]=-1;
}
private:
bool judge(int y,int x){
if(x>0 && x<=n && y>0 && y<=n && map[y][x]==0)
return true;
else
return false;
}
public:
void set(int y,int x,int t){
if(t==n*n){
map[y][x]=t;
cout<<"one possible answer:"<for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]<10)
cout<<" ";
cout<<" "<