新编计算机导论 课件 7-2-典型问题的几种程序实现

程序设计语言新编计算机导论典型问题的几种程序实现本节将选择当前比较流行的几种程序设计语言，给出求解若干典型问题的相应程序。3.典型问题的几种程序实现冒泡排序问题的C++实现冒泡排序：基本思想是对相邻元素进行比较，并根据比较的结果交换位置，从而逐步由任意序列变为有序序列。若有n个待排数字，则需要进行n-1轮排序，第i轮需要比较n-i次（i从1开始）。图1冒泡排序3.典型问题的几种程序实现冒泡排序问题的C++实现#include<iostream>usingnamespacestd;

//冒泡排序函数，a为待排序的数组，n为数组中的元素个数voidBubbleSort(int*a,intn){ inttemp; for(inti=0;i<n-1;i++) //一共需比较n-1趟

{ for(intj=0;j<n-i-1;j++) //每趟需进行n-i-1次的两两比较 if(a[j]>a[j+1]) //相邻元素两两比较，若逆序则交换

{temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;}}}//主函数intmain(){intarr[]={8,5,3,9,2,7};BubbleSort(arr,6); //调用冒泡排序函数for(inti=0;i<6;i++) cout<<arr[i]<<""; //输出排序后的结果cout<<endl;return0;}算法1冒泡排序算法

3.典型问题的几种程序实现汉诺塔问题的Java实现汉诺塔问题：当A杆上只有一个盘子时只要把这个盘子直接移到C杆即可；当A杆上两个盘子时，先把1号盘移到B杆，再把2号盘移到C杆，最后再把B杆上的1号盘移到C杆即可。假设要移动的盘子共64个，此时可以先将上方的63个盘子看成一个整体，这样就相当于只有两个盘子，问题就变得简单起来，相当于完成两个盘子的转移就行了。对于63个盘子的移动，采用与之前一样的解决方案，先完成前62个盘子的移动，逐步前推至62、61、60、......、2、1，直至完成所有盘子的移动。图2汉诺塔问题3.典型问题的几种程序实现importjavax.swing.JOptionPane; //导入一个简单的交互窗口包publicclassHanoiTemple{

/** *@paramargs publicstaticvoidmain(String[]args){

Stringn=JOptionPane.showInputDialog("请输入要移动的盘数：");HanoiTempleht=newHanoiTemple(); //新建一个汉诺塔对象

ht.move(Integer.parseInt(n),'A','B','C'); //移动函数

} publicvoidmove(intn,chara,charb,charc){ //递归函数，汉诺塔的实现

if(n==1){ //若当前只用移动一个盘，直接移动过去System.out.println("movefrom"+a+"to"+c); }else{ move(n-1,a,c,b); //递归调用从a移动到b move(1,a,b,c); //当前只有一个盘，从a柱移动到c柱

move(n-1,b,a,c); //递归调用从b移动到c

}}}算法2汉诺塔问题汉诺塔问题的Java实现3.典型问题的几种程序实现国王的婚姻问题的Python实现国王的婚姻问题：本质上就是简单的计算总因子个数的问题，只要求出待求数据num的总因子个数即可。代码采用的是国王的方法，即穷举所有可能的因子。大臣的方法实际是一种并行计算的思想，当同学们对操作系统有了一定的了解之后不难理解，具体实现请参考专业操作系统设计的书籍。3.典型问题的几种程序实现国王的婚姻问题的Python实现num=int(input("inputnumber:")) #输入待求数i=1 #被除数number=0 #因子个数ifnum>=2: #如果待求数为1，则直接跳出whilei<=num: #循环ifnum%i==0: #判断是否能整除，整除则为num的因子number+=1i+=1print("总因字数：",number) #输出总因子数算法3国王的婚姻问题3.典型问题的几种程序实现国王的婚姻问题的Python实现算法优化：例如当num可以被整除时，表示必然存在两个因子，即可以直接number+=2，此时动态的修改while语句的判断条件为两个因子较大的一个，即可大大降低时间复杂度。num=int(input("inputnumber:")) #输入待求数max=num #循环上界i=1

#被除数number=0

#因子个数ifnum>=2:

#如果待求数为1，则直接跳出whilei<maxandi<num/2: #循环i需要小于循环上界max,#且小于num/2(因子成对出现)ifnum%i==0: #判断是否能整除，整除则为num的因子number=number+2ifi**2<numelsenumber+1#判断如果num为#平方数,则该因子只