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,i