c/c++快乐算法第三天
c/c++感受算法快乐（3）
开始时间2023-04-16 22:21:10
结束时间2023-04-17 00:09:34
前言：很好，这周就要结束了，大家都回学校了么，嘻嘻。回顾一下昨天的算法题，1.4抓交通肇事犯运用枚举模拟，1.5兔子产子问题运用迭代循环，1.6牛顿迭代法求方程根迭代循环，1.7最佳存款问题迭代循环。什么是迭代？对计算机特定程序中需要反复执行的子程序（一组指令），进行一次重复，即重复执行程序中的循环，直到满足某条件为止，亦称为迭代。快来看看今天的问题叭！
第一章 趣味算法入门
第八题 冒泡排序
一.问题描述
二.设计思路
有输入，并且为自行输入的n个整数序列。这里我们需要用到冒泡排序，冒泡排序是什么？它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成，如同汽水中的气泡最终会冒到顶部一样顾名冒泡排序。冒泡排序总的平均时间复杂度为
三.流程图
四.源代码
#include<stdio.h> int main() { int n; scanf("%d",&n); int a[n]; int i=0,j=0,temp; for(i=0;i<n;i++) { scanf("%d",&a[i]); } for(i=1;i<n;i++) { for(j=0;j<n-i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=0;i<n;i++) { printf("%d\t",a[i]); } return 0; }
五.运行结果
第九题 折半查找
一.问题描述
二.设计思路
三.流程图
四.源代码
#include<stdio.h> int main() { int arr[]={3,4,10,13,33,42,46,63,76,78,95,96,120}; int size=sizeof(arr)/sizeof(arr[0]);//数组的长度 int x,middle; scanf("%d",&x);//输入要查找的数 int left=0; int right=size; while(left<=right)//循环条件 { middle=(left+right)/2;//中间数 if(arr[middle]<x) { left=middle+1;//要查找的数在中间数的右边，左端加一即向右移，缩小范围 } else if(arr[middle]>x) { right=middle-1;//要查找的数在中间数的左边，右端加一即向左移，缩小范围 } else if(arr[middle]=x)//最后当中间数=要查找的数时查找完毕 { printf("%d在arr[%d]\n位置:第%d个数",x,middle,middle+1); break; } } if(left>right)//当left>right时证明此范围内不存在要查找的数 { printf("查无此数\n"); } return 0; }
五.运行结果
第十题 数值转换
一.问题描述
二.设计思路
三.流程图
四.源代码
#include<iostream> using namespace std; #define Max 101 //限定数组最大长度 int char_to_num(char ch); //返回字符对应的数字 char num_to_char(int num); //返回数字对应的字符 long source_to_decimal(char temp[],int source); //返回由原数转换成的十进制数 int decimal_to_object(char temp[],long decimal_num,int object); //返回转换成目标进制的数组长度 void output(char temp[],int length); //将字符数组逆序输出 int main(){ int source; //存储原来的进制 int object; //存储目标进制 int length; //存储转化后的数组长度 long decimal_num; //存储转换成的十进制数 char temp[Max]; //存储待转化的数值 和转化后的数值 int flag=1; //是否结束程序 while(flag) { cout<<"转换前的数是："; cin>>temp; cout<<"转换前的进制是："; cin>>source; cout<<"转换后的进制是"; cin>>object; cout<<"转换后的数值是："; decimal_num=source_to_decimal(temp,source); length=decimal_to_object(temp,decimal_num,object); output(temp,length); cout<<"继续请输入1，否则输入0"; cin>>flag; } } int char_to_num(char ch) { if(ch>='0'&&ch<='9') return ch-'0'; //0~9 else return ch-'A'+10;//大于10的数字 } char num_to_char(int num) { if(num>=0&&num<=9) return (char)('0'+num-0); else return (char)('A'+num-10); } long source_to_decimal(char temp[],int source) { long decimal_num=0; int length; int i; for(i=0;temp[i]!='\0';i++); length=i; for(i=0;i<length-1;i++) decimal_num=(decimal_num*source)+char_to_num(temp[i]); return decimal_num; } int decimal_to_object(char temp[],long decimal_num,int object) { int i=0; while(decimal_num) { temp[i]=num_to_char(decimal_num%object); decimal_num=decimal_num/object; i++; } temp[i]='\0'; return i; } void output(char temp[],int length) { int i; for(i=length-1;i>=0;i--) cout<<temp[i]; cout<<endl; }
五.运行结果