1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<time.h> 4 int path[9][9]; 5 int s1() 6 { 7 int choose,n,i; 8 long result,start,end,a=0,b=1,c; 9 10 printf(" 进入Fibonacci序列问题 "); 11 printf("1.用两种方法分别求最大的n "); 12 printf("2.输入n求Fibonacci数 "); 13 printf("请选择："); 14 scanf("%d",&choose); 15 if(choose==1) 16 { 17 n=1; 18 start=clock(); 19 do 20 { 21 result=a+b; 22 a=b; 23 b=result; 24 printf("第%d个Fibonacci数：%d ",n,a); 25 n++; 26 }while(result>=a); 27 end=clock(); 28 printf(" 迭代求得最大的n为%d,用时%d毫秒 ",n-1,end-start); 29 30 n=1,a=0,b=1; 31 start=clock(); 32 n=F(a,b,n); 33 end=clock(); 34 printf(" 递归求得最大的n为%d,用时%d毫秒 ",n,end-start); 35 } 36 else if(choose==2) 37 { 38 printf(" 请输入一个整数n:"); 39 scanf("%d",&n); 40 if(n<0) 41 printf("请输入正数！"); 42 else if(n>0&&n<3) 43 printf("Fibonacci(%d)=1 ",n); 44 else if(n>2) 45 { 46 for(i=1;i<n;i++) 47 { 48 result=a+b; 49 a=b; 50 b=result; 51 } 52 printf("Fibonacci(%d)=%d ",n,result); 53 } 54 } 55 printf(" 退出并返回主菜单 "); 56 } 57 58 int F(int a,int b,int n) 59 { 60 if((a+b)<b) 61 { 62 return n; 63 } 64 else 65 { 66 printf("第%d个Fibonacci数：%d ",n,b); 67 F(b,a+b,n+1); 68 } 69 } 70 71 void s2() 72 { 73 int n,choose,i,j,k,a[10][10],b[10][10],c[10][10]; 74 printf(" 进入矩阵相乘问题 "); 75 printf("请输入需要计算的矩阵阶数(10以内)："); 76 scanf("%d",&n); 77 if(n<=0) 78 printf("请输入正数！"); 79 else if(n>0) 80 { 81 printf(" 1.随机生成矩阵数据 "); 82 printf("2.手动输入矩阵数据 "); 83 printf("请选择："); 84 scanf("%d",&choose); 85 if(choose==1) 86 { 87 srand(time(0)); 88 for(i=0;i<n;i++) 89 for(j=0;j<n;j++) 90 a[i][j]=rand()%10; 91 for(i=0;i<n;i++) 92 for(j=0;j<n;j++) 93 b[i][j]=rand()%10; 94 } 95 else if(choose==2) 96 { 97 for(i=0;i<n;i++) 98 for(j=0;j<n;j++) 99 { 100 printf("a矩阵第%d行第%d列："); 101 scanf("%d",&a[i][j]); 102 } 103 for(i=0;i<n;i++) 104 for(j=0;j<n;j++) 105 { 106 printf("b矩阵第%d行第%d列："); 107 scanf("%d",&b[i][j]); 108 } 109 } 110 //输出当前两个矩阵 111 printf(" a矩阵： "); 112 for(i=0;i<n;i++) 113 { 114 for(j=0;j<n;j++) 115 printf("%d ",a[i][j]); 116 printf(" "); 117 } 118 printf(" b矩阵： "); 119 for(i=0;i<n;i++) 120 { 121 for(j=0;j<n;j++) 122 printf("%d ",b[i][j]); 123 printf(" "); 124 } 125 //选择算法 126 printf(" 1.蛮力法计算 "); 127 printf("2.分治法计算 "); 128 printf("请选择："); 129 scanf("%d",&choose); 130 if(choose==1) 131 { 132 for(i=0;i<n;i++) 133 for(j=0;j<n;j++) 134 c[i][j]=0; 135 for(i=0;i<n;i++) 136 for(j=0;j<n;j++) 137 { 138 for(k=0;k<n;k++) 139 c[i][j]=c[i][j]+a[i][k]*b[k][j]; 140 } 141 printf(" 结果矩阵： "); 142 for(i=0;i<n;i++) 143 { 144 for(j=0;j<n;j++) 145 printf("%-5d",c[i][j]); 146 printf(" "); 147 } 148 } 149 else if(choose==2) 150 {} 151 152 } 153 printf(" 退出并返回主菜单 "); 154 } 155 156 void s3() 157 { 158 int i,x,choose,c[7]; 159 printf(" 进入8枚硬币问题 "); 160 printf("1.随机生成假币 "); 161 printf("2.手动输入假币编号（1-8） "); 162 printf("请选择："); 163 scanf("%d",&choose); 164 if(choose==1) 165 { 166 srand(time(0)); 167 x=rand()%7+1; 168 } 169 else if(choose==2) 170 { 171 scanf("%d",&x); 172 173 } 174 175 for(i=0;i<7;i++) 176 c[i]=1; 177 c[x-1]=2; 178 179 if((c[0]+c[2]+c[4])==(c[1]+c[3]+c[5])) 180 { 181 printf("1、3、5号硬币和2、4、6号硬币一样重 "); 182 if(c[6]==c[4]) 183 { 184 printf("7号硬币和5号硬币一样重 "); 185 printf("8号硬币是假币 "); 186 } 187 else 188 { 189 printf("7号硬币和5号硬币不一样重 "); 190 printf("7号硬币是假币 "); 191 } 192 } 193 else 194 { 195 printf("1、3、5号硬币和2、4、6号硬币不一样重 "); 196 if((c[0]+c[2])==(c[1]+c[3])) 197 { 198 printf("1、3号硬币和2、4号硬币一样重 "); 199 if(c[4]==c[2]) 200 { 201 printf("5号硬币和3号硬币一样重 "); 202 printf("6号硬币是假币 "); 203 } 204 else 205 { 206 printf("5号硬币和3号硬币不一样重 "); 207 printf("5号硬币是假币 "); 208 } 209 } 210 else 211 { 212 printf("1、3号硬币和2、4号硬币不一样重 "); 213 if(c[0]==c[1]) 214 { 215 printf("1号硬币和2号硬币一样重 "); 216 if(c[0]==c[2]) 217 { 218 printf("1号硬币和3号硬币一样重 "); 219 printf("4号硬币是假币 "); 220 } 221 else 222 { 223 printf("1号硬币和3号硬币不一样重 "); 224 printf("3号硬币是假币 "); 225 } 226 } 227 else 228 { 229 printf("1号硬币和2号硬币不一样重 "); 230 if(c[0]==c[2]) 231 { 232 printf("1号硬币和3号硬币一样重 "); 233 printf("2号硬币是假币 "); 234 } 235 else 236 { 237 printf("1号硬币和3号硬币不一样重 "); 238 printf("1号硬币是假币 "); 239 } 240 } 241 } 242 } 243 } 244 245 void HAd1(int a[],int i,int nLength) 246 { 247 int Child; 248 int nTemp; 249 for(;2*i+1<nLength;i=Child) 250 { 251 252 Child=2*i+1; 253 254 if(Child<nLength-1&&a[Child+1]>a[Child]) 255 Child++; 256 257 if(a[i]<a[Child]) 258 { 259 nTemp=a[i]; 260 a[i]=a[Child]; 261 a[Child]=nTemp; 262 } 263 } 264 } 265 266 267 /*void kkk() 268 { 269 int a,b,c[2000]; 270 c[0]=b+a; 271 printf("# "); 272 for(a=0;a<2000;a++) 273 if(b) 274 c[a]=++b; 275 }*/ 276 277 void s4() 278 { 279 int i,t,ch,choose,ma[9]; 280 long start,end; 281 short Auto[1500]; 282 283 //for(i=2000;i>=0;i--) 284 //kkk(); 285 286 printf(" 进入堆排序问题 "); 287 printf("1.手动输入检测可用性（10个数据） "); 288 printf("2.随机生成2000个数据检测时间效率 "); 289 printf("请选择："); 290 scanf("%d",&choose); 291 if(choose==1) 292 { 293 printf("每次回车输入一个数据： "); 294 for(i=0;i<10;i++) 295 scanf("%d",&ma[i]); 296 for(i=4;i>=0;i--) 297 HAd1(ma,i,10); 298 for(i=8;i>0;--i) 299 { 300 t=ma[0]; 301 ma[0]=ma[i]; 302 ma[i]=t; 303 HAd1(ma,0,i); 304 } 305 printf("排序结果： "); 306 for(i=0;i<10;i++) 307 printf("%d ",ma[i]); 308 309 } 310 else if(choose==2) 311 { 312 printf("# "); 313 srand(time(0)); 314 315 for(i=0;i<150;i++) 316 Auto[i]=rand()%200; 317 318 printf("# "); 319 start=clock(); 320 321 322 for(i=74;i>=0;i--) 323 { 324 for(;i*2+1<150;i=ch) 325 { 326 ch=i*2+1; 327 if(ch+1<150&&Auto[ch+1]>Auto[ch]) 328 ch++; 329 if(Auto[i]<Auto[ch]) 330 { 331 t=Auto[i]; 332 Auto[i]=Auto[ch]; 333 Auto[ch]=t; 334 } 335 } 336 } 337 printf("# "); 338 //HAd1(ma,i,1500); 339 for(i=149;i>0;--i) 340 { 341 t=ma[0]; 342 ma[0]=ma[i]; 343 ma[i]=t; 344 HAd1(ma,0,i); 345 } 346 347 end=clock(); 348 349 printf("所花时间为%d ",end-start); 350 } 351 printf(" 退回主菜单 "); 352 } 353 354 int mpt(int beg,int end) 355 { 356 if(path[beg][end]>=0) 357 { 358 mpt(beg,path[beg][end],path); 359 mpt(path[beg][end],end,path); 360 } 361 else 362 printf("->%s",end+97); 363 } 364 365 void s5() 366 { 367 int i,j,k,beg,end,x,choose,map[9][9]; 368 char tale; 369 srand(time(0)); 370 371 for(i=0;i<10;i++) 372 for(j=0;j<10;j++) 373 map[i][j]=10; 374 for(i=0;i<10;i++) 375 for(j=0;j<10;j++) 376 path[i][j]=-1; 377 378 printf(" 进入最短路径问题 "); 379 printf("1.随机生成图(5个点权值1-9) "); 380 printf("2.手动输入图 "); 381 printf("请选择："); 382 scanf("%d",&choose); 383 384 if(choose==1) 385 { 386 for(i=0;i<5;i++) 387 { 388 for(j=0;j<5;j++) 389 { 390 if(rand()%9<3) 391 map[i][j]=rand()%9+1; 392 } 393 map[i][i+1]=rand()%9+1; 394 map[i][i]=0; 395 } 396 map[4][0]=rand()%9+1; 397 } 398 else if(choose==2) 399 { 400 x; 401 } 402 // 403 for(i=0;i<5;i++) 404 { 405 for(j=0;j<5;j++) 406 if(map[i][j]<10) 407 printf("%d ",map[i][j]); 408 else 409 printf("x "); 410 printf(" "); 411 } 412 printf("#"); 413 for(k=0;k<10;k++) 414 for(i=0;i<10;i++) 415 for(j=0;j<10;j++) 416 { 417 if(map[i][k]+map[k][j]<map[i][j]) 418 { 419 map[i][j]=map[i][k]+map[k][j]; 420 path[i][j]=k; 421 } 422 } 423 printf(" 请输入起点（小写字母）："); 424 scanf("%s",&tale); 425 beg=tale-97; 426 printf("请输入终点（小写字母）："); 427 scanf("%s",&tale); 428 end=tale-97; 429 printf("#"); 430 x=map[beg][end]; 431 tale=beg+97; 432 printf("#"); 433 printf("最短距离为%d,最短路径为： %s",x,tale); 434 printf("#"); 435 mpt(beg,end); 436 } 437 438 void main() 439 { 440 int k; 441 printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); 442 printf(" 《算法设计与分析》实验 "); 443 printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); 444 while(1) 445 { 446 447 printf(" 1. 算法分析基础——Fibonacci序列问题 "); 448 printf("2. 分治法在数值问题中的应用——矩阵相乘问题 "); 449 printf("3. 减治法在组合问题中的应用——8枚硬币问题 "); 450 printf("4. 变治法在排序问题中的应用——堆排序问题 "); 451 printf("5. 动态规划法在图问题中的应用——全源最短路径问题 "); 452 printf("99. 退出本实验 "); 453 printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); 454 printf("请输入您所要执行的操作（1，2，3，4，5，99）："); 455 456 scanf("%d",&k); 457 switch(k) 458 { 459 case 1: 460 s1(); 461 break; 462 case 2: 463 s2(); 464 break; 465 case 3: 466 s3(); 467 break; 468 case 4: 469 s4(); 470 break; 471 case 5: 472 s5(); 473 break; 474 case 99: 475 exit(0); 476 default: 477 exit(1); 478 } 479 480 } 481 }
#include<stdio.h> #include<stdlib.h> #include<time.h> int path[9][9]; int s1() { int choose,n,i; long result,start,end,a=0,b=1,c; printf(" 进入Fibonacci序列问题 "); printf("1.用两种方法分别求最大的n "); printf("2.输入n求Fibonacci数 "); printf("请选择："); scanf("%d",&choose); if(choose==1) { n=1; start=clock(); do { result=a+b; a=b; b=result; printf("第%d个Fibonacci数：%d ",n,a); n++; }while(result>=a); end=clock(); printf(" 迭代求得最大的n为%d,用时%d毫秒 ",n-1,end-start); n=1,a=0,b=1; start=clock(); n=F(a,b,n); end=clock(); printf(" 递归求得最大的n为%d,用时%d毫秒 ",n,end-start); } else if(choose==2) { printf(" 请输入一个整数n:"); scanf("%d",&n); if(n<0) printf("请输入正数！"); else if(n>0&&n<3) printf("Fibonacci(%d)=1 ",n); else if(n>2) { for(i=1;i<n;i++) { result=a+b; a=b; b=result; } printf("Fibonacci(%d)=%d ",n,result); } } printf(" 退出并返回主菜单 "); } int F(int a,int b,int n) { if((a+b)<b) { return n; } else { printf("第%d个Fibonacci数：%d ",n,b); F(b,a+b,n+1); } } void s2() { int n,choose,i,j,k,a[10][10],b[10][10],c[10][10]; printf(" 进入矩阵相乘问题 "); printf("请输入需要计算的矩阵阶数(10以内)："); scanf("%d",&n); if(n<=0) printf("请输入正数！"); else if(n>0) { printf(" 1.随机生成矩阵数据 "); printf("2.手动输入矩阵数据 "); printf("请选择："); scanf("%d",&choose); if(choose==1) { srand(time(0)); for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][j]=rand()%10; for(i=0;i<n;i++) for(j=0;j<n;j++) b[i][j]=rand()%10; } else if(choose==2) { for(i=0;i<n;i++) for(j=0;j<n;j++) { printf("a矩阵第%d行第%d列："); scanf("%d",&a[i][j]); } for(i=0;i<n;i++) for(j=0;j<n;j++) { printf("b矩阵第%d行第%d列："); scanf("%d",&b[i][j]); } } //输出当前两个矩阵 printf(" a矩阵： "); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d ",a[i][j]); printf(" "); } printf(" b矩阵： "); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d ",b[i][j]); printf(" "); } //选择算法 printf(" 1.蛮力法计算 "); printf("2.分治法计算 "); printf("请选择："); scanf("%d",&choose); if(choose==1) { for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=0; for(i=0;i<n;i++) for(j=0;j<n;j++) { for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } printf(" 结果矩阵： "); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%-5d",c[i][j]); printf(" "); } } else if(choose==2) {} } printf(" 退出并返回主菜单 "); } void s3() { int i,x,choose,c[7]; printf(" 进入8枚硬币问题 "); printf("1.随机生成假币 "); printf("2.手动输入假币编号（1-8） "); printf("请选择："); scanf("%d",&choose); if(choose==1) { srand(time(0)); x=rand()%7+1; } else if(choose==2) { scanf("%d",&x); } for(i=0;i<7;i++) c[i]=1; c[x-1]=2; if((c[0]+c[2]+c[4])==(c[1]+c[3]+c[5])) { printf("1、3、5号硬币和2、4、6号硬币一样重 "); if(c[6]==c[4]) { printf("7号硬币和5号硬币一样重 "); printf("8号硬币是假币 "); } else { printf("7号硬币和5号硬币不一样重 "); printf("7号硬币是假币 "); } } else { printf("1、3、5号硬币和2、4、6号硬币不一样重 "); if((c[0]+c[2])==(c[1]+c[3])) { printf("1、3号硬币和2、4号硬币一样重 "); if(c[4]==c[2]) { printf("5号硬币和3号硬币一样重 "); printf("6号硬币是假币 "); } else { printf("5号硬币和3号硬币不一样重 "); printf("5号硬币是假币 "); } } else { printf("1、3号硬币和2、4号硬币不一样重 "); if(c[0]==c[1]) { printf("1号硬币和2号硬币一样重 "); if(c[0]==c[2]) { printf("1号硬币和3号硬币一样重 "); printf("4号硬币是假币 "); } else { printf("1号硬币和3号硬币不一样重 "); printf("3号硬币是假币 "); } } else { printf("1号硬币和2号硬币不一样重 "); if(c[0]==c[2]) { printf("1号硬币和3号硬币一样重 "); printf("2号硬币是假币 "); } else { printf("1号硬币和3号硬币不一样重 "); printf("1号硬币是假币 "); } } } } } void HAd1(int a[],int i,int nLength) { int Child; int nTemp; for(;2*i+1<nLength;i=Child) { Child=2*i+1; if(Child<nLength-1&&a[Child+1]>a[Child]) Child++; if(a[i]<a[Child]) { nTemp=a[i]; a[i]=a[Child]; a[Child]=nTemp; } } } /*void kkk() { int a,b,c[2000]; c[0]=b+a; printf("# "); for(a=0;a<2000;a++) if(b) c[a]=++b; }*/ void s4() { int i,t,ch,choose,ma[9]; long start,end; short Auto[1500]; //for(i=2000;i>=0;i--) //kkk(); printf(" 进入堆排序问题 "); printf("1.手动输入检测可用性（10个数据） "); printf("2.随机生成2000个数据检测时间效率 "); printf("请选择："); scanf("%d",&choose); if(choose==1) { printf("每次回车输入一个数据： "); for(i=0;i<10;i++) scanf("%d",&ma[i]); for(i=4;i>=0;i--) HAd1(ma,i,10); for(i=8;i>0;--i) { t=ma[0]; ma[0]=ma[i]; ma[i]=t; HAd1(ma,0,i); } printf("排序结果： "); for(i=0;i<10;i++) printf("%d ",ma[i]); } else if(choose==2) { printf("# "); srand(time(0)); for(i=0;i<150;i++) Auto[i]=rand()%200; printf("# "); start=clock(); for(i=74;i>=0;i--) { for(;i*2+1<150;i=ch) { ch=i*2+1; if(ch+1<150&&Auto[ch+1]>Auto[ch]) ch++; if(Auto[i]<Auto[ch]) { t=Auto[i]; Auto[i]=Auto[ch]; Auto[ch]=t; } } } printf("# "); //HAd1(ma,i,1500); for(i=149;i>0;--i) { t=ma[0]; ma[0]=ma[i]; ma[i]=t; HAd1(ma,0,i); } end=clock(); printf("所花时间为%d ",end-start); } printf(" 退回主菜单 "); } int mpt(int beg,int end) { if(path[beg][end]>=0) { mpt(beg,path[beg][end],path); mpt(path[beg][end],end,path); } else printf("->%s",end+97); } void s5() { int i,j,k,beg,end,x,choose,map[9][9]; char tale; srand(time(0)); for(i=0;i<10;i++) for(j=0;j<10;j++) map[i][j]=10; for(i=0;i<10;i++) for(j=0;j<10;j++) path[i][j]=-1; printf(" 进入最短路径问题 "); printf("1.随机生成图(5个点权值1-9) "); printf("2.手动输入图 "); printf("请选择："); scanf("%d",&choose); if(choose==1) { for(i=0;i<5;i++) { for(j=0;j<5;j++) { if(rand()%9<3) map[i][j]=rand()%9+1; } map[i][i+1]=rand()%9+1; map[i][i]=0; } map[4][0]=rand()%9+1; } else if(choose==2) { x; } // for(i=0;i<5;i++) { for(j=0;j<5;j++) if(map[i][j]<10) printf("%d ",map[i][j]); else printf("x "); printf(" "); } printf("#"); for(k=0;k<10;k++) for(i=0;i<10;i++) for(j=0;j<10;j++) { if(map[i][k]+map[k][j]<map[i][j]) { map[i][j]=map[i][k]+map[k][j]; path[i][j]=k; } } printf(" 请输入起点（小写字母）："); scanf("%s",&tale); beg=tale-97; printf("请输入终点（小写字母）："); scanf("%s",&tale); end=tale-97; printf("#"); x=map[beg][end]; tale=beg+97; printf("#"); printf("最短距离为%d,最短路径为： %s",x,tale); printf("#"); mpt(beg,end); } void main() { int k; printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); printf(" 《算法设计与分析》实验 "); printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); while(1) { printf(" 1. 算法分析基础——Fibonacci序列问题 "); printf("2. 分治法在数值问题中的应用——矩阵相乘问题 "); printf("3. 减治法在组合问题中的应用——8枚硬币问题 "); printf("4. 变治法在排序问题中的应用——堆排序问题 "); printf("5. 动态规划法在图问题中的应用——全源最短路径问题 "); printf("99. 退出本实验 "); printf("－－－－－－－－－－－－－－－－－－－－－－－－－ "); printf("请输入您所要执行的操作（1，2，3，4，5，99）："); scanf("%d",&k); switch(k) { case 1: s1(); break; case 2: s2(); break; case 3: s3(); break; case 4: s4(); break; case 5: s5(); break; case 99: exit(0); default: exit(1); } } }