c/c++感受演算法快樂（3） 開始時間2023-04-16 22:21:10 結束時間2023-04-17 00:09:34 前言：很好，這周就要結束了，大家都回學校了麽，嘻嘻。回顧一下昨天的演算法題，1.4抓交通肇事犯運用枚舉模擬，1.5兔子產子問題運用迭代迴圈，1.6牛頓迭代法求方程根迭代迴圈，1 ...
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; }
五.運行結果
