经典算法程序实现2(基础篇二：解析)

二分法（Binary Search）是一种常用的搜索算法，特别适用于有序数组或列表。

其基本思想是通过比较中间元素与目标值的大小关系，缩小搜索范围，直到找到目标值为止。

以下是一个经典的二分法例题及其讲解：**问题描述：**给定一个有序数组 `arr` 和目标值 `target`，要求在数组中找到目标值的索引，如果目标值不存在，则返回 -1。

**二分法解决方案：**```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2 # 计算中间索引if arr[mid] == target:return mid # 找到目标值，返回索引elif arr[mid] < target:left = mid + 1 # 缩小搜索范围到右半部分else:right = mid - 1 # 缩小搜索范围到左半部分return -1 # 目标值不存在# 示例arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]target = 6result = binary_search(arr, target)print("目标值 {} 在数组中的索引是：{}".format(target, result))```**解释：**1. 初始化左右两个指针 `left` 和 `right` 分别指向数组的第一个和最后一个元素。

2. 在循环中，计算中间索引 `mid`。

3. 比较中间元素与目标值的大小关系：- 如果中间元素等于目标值，则直接返回中间索引。

- 如果中间元素小于目标值，说明目标值可能在右半部分，更新 `left`。

- 如果中间元素大于目标值，说明目标值可能在左半部分，更新 `right`。

4. 重复步骤2和步骤3，直到找到目标值或者 `left` 大于`right`。

C语言经典算法100例(1)(2007-08-15 15:09:22)C 语言编程经典 100 例【程序1】题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。

组成所有的排列后再去掉不满足条件的排列。

2.程序源代码：main(){int i,j,k;printf(“\n“);for(i=1;i〈5;i++) ／*以下为三重循环*/for(j=1;j〈5;j++)for (k=1;k〈5;k++){if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/printf(“%d,%d,%d\n“,i,j,k);}}【程序2】题目：企业发放的奖金根据利润提成。

利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？1.程序分析：请利用数轴来分界，定位。

注意定义时需把奖金定义成长整型。

2.程序源代码：main(){long int i;int bonus1,bonus2,bonus4,bonus6,bonus10,bonus;scanf(“%ld“,&i);bonus1=100000*0.1;bonus2=bonus1+100000*0.75;bonus4=bonus2+200000*0.5;bonus6=bonus4+200000*0.3;bonus10=bonus6+400000*0.15;if(i〈=100000)bonus=i*0.1;else if(i〈=200000)bonus=bonus1+(i-100000)*0.075;else if(i〈=400000)bonus=bonus2+(i-200000)*0.05;else if(i〈=600000)bonus=bonus4+(i-400000)*0.03;else if(i〈=1000000)bonus=bonus6+(i-600000)*0.015;elsebonus=bonus10+(i-1000000)*0.01;printf(“bonus=%d“,bonus);}【程序3】题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？1.程序分析：在10万以内判断，先将该数加上100后再开方，再将该数加上268后再开方，如果开方后的结果满足如下条件，即是结果。

深入探究算法原理引言在计算机科学领域，算法是解决问题的一系列步骤或指令。

算法是计算机程序的核心，它们决定了程序的效率和最终结果。

在今天的文章中，我们将深入探究算法的原理，了解它们是如何工作的，以及为什么一些算法比其他算法更高效。

什么是算法算法可以被认为是将输入数据转化为期望输出的一组定义良好的指令。

一个好的算法应该是可执行的、确定性的和有限的。

算法的输入可以是任何数据类型，包括数字、字符串和图像等。

而输出通常是一个解决方案、一个决策或一个转换后的数据。

常见的算法类型在计算机科学中，有许多不同类型的算法。

下面列出了一些常见的算法类型：1.排序算法排序算法是将一组元素按照特定规则进行排序的算法。

常见的排序算法包括冒泡排序、插入排序、选择排序和快速排序等。

这些算法的不同之处在于它们所使用的比较和交换元素的策略。

2.搜索算法搜索算法是在一组数据中查找特定元素或属性的算法。

常见的搜索算法包括线性搜索、二分搜索和哈希搜索等。

这些算法的不同之处在于它们所使用的搜索策略和数据结构。

3.图算法图算法是解决图相关问题的算法。

图是由一组节点和连接它们的边组成的数据结构。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）和最短路径算法等。

这些算法的不同之处在于它们所使用的遍历或搜索策略。

4.动态规划算法动态规划算法通过将问题分解为子问题，并保存已解决的子问题的解，来解决复杂的问题。

常见的动态规划算法包括斐波那契数列、最长公共子序列和背包问题等。

这些算法的不同之处在于它们所使用的分解和组合子问题的策略。

算法的性能评估在选择使用哪个算法解决问题时，我们需要比较它们的性能。

以下是一些常用的性能指标：1.时间复杂度时间复杂度是指算法在最坏情况下执行所需要的时间。

在表示时间复杂度时，我们通常使用大O符号。

例如，O(n)表示算法的时间复杂度为线性级别，O(n^2)表示算法的时间复杂度为平方级别。

2.空间复杂度空间复杂度是指算法在执行过程中所需要的额外空间。

用程序算最大公因数的方法1. 引言1.1 什么是最大公因数最大公因数是指两个或多个整数共有的约数中最大的一个。

在数学中，最大公因数通常用最大公因数符号gcd(a, b)来表示，其中a和b 为整数。

最大公因数的计算在数论和计算机科学中都有着重要的应用。

最大公因数在数论中常常用来分解整数或解决同余方程，而在计算机科学中则经常用于优化算法或数据结构的设计。

计算最大公因数可以帮助我们简化问题、提高计算效率，甚至发现问题的隐藏规律。

最大公因数的概念在数学中十分重要，它不仅有助于我们理解数学规律，还有利于我们解决实际问题中的计算难题。

对最大公因数的研究和计算方法的探索具有重要意义，不仅可以帮助我们更好地理解数学知识，在实际应用中也能大大提高计算效率。

1.2 为什么需要计算最大公因数计算最大公因数在数学和计算机领域中有着重要的应用价值。

最大公因数是两个数中能够整除它们的最大正整数，是整数的一个重要属性。

计算最大公因数可以帮助我们了解和分析数学问题中的数值关系，为解决问题提供重要的参考。

计算最大公因数在数论、代数、几何等数学领域中有着广泛的应用，如简化分数、化简代数表达式、寻找数字规律等。

而在计算机领域中，计算最大公因数可以帮助我们优化算法和提高代码效率，特别是在设计和实现数值计算程序时，经常需要用到最大公因数。

最大公因数还可以用于密码学、数据传输等领域，确保数据的安全性和正确性。

理解和掌握计算最大公因数的方法对于我们的数学学习和计算机编程至关重要。

2. 正文2.1 辗转相除法计算最大公因数辗转相除法计算最大公因数是一种古老而又简单有效的算法。

其基本原理是通过连续地用两个数中较小的数去除以两个数中较大的数，然后用余数去除之前的较小的数，直到余数为0为止。

此时最后一个非零余数即为最大公因数。

举个例子来说明辗转相除法的步骤：我们要计算45和15的最大公因数。

首先用45除以15，商为3，余数为0，所以15即为最大公因数。

10个经典的C语言基础算法及代码1.冒泡排序算法冒泡排序是一种简单但效率较低的排序算法，在每一轮遍历中比较相邻的两个元素，如果顺序不正确则交换它们，直到整个数组有序为止。

```cvoid bubbleSort(int arr[], int n)for (int i = 0; i < n-1; i++)for (int j = 0; j < n-1-i; j++)if (arr[j] > arr[j+1])int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}```2.选择排序算法选择排序是一种简单直观的排序算法，它每次从待排序的数组中选择最小（或最大）的元素，并放到已排序的数组末尾。

```cvoid selectionSort(int arr[], int n)for (int i = 0; i < n-1; i++)int min_index = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[min_index])min_index = j;}}int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}```3.插入排序算法插入排序的基本思想是将数组分为已排序和未排序两部分，每次将未排序的元素插入到已排序的合适位置。

```cvoid insertionSort(int arr[], int n)for (int i = 1; i < n; i++)int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key)arr[j+1] = arr[j];j--;}arr[j+1] = key;}```4.快速排序算法快速排序使用分治法的思想，每次选择一个基准元素，将小于基准的元素放到左边，大于基准的元素放到右边，然后递归地对左右两个子数组进行排序。

递归算法及经典递归例子代码实现递归算法是一种在函数体内调用函数本身的算法。

通过递归，问题可以被分解为规模更小的子问题，直到达到基本情况，然后将所有的子问题的解合并起来，得到原始问题的解。

递归算法的实现通常包含两个要素：基本情况和递归调用。

基本情况是指不能再进一步分解的情况，一般是针对问题的最小输入。

递归调用是指在解决子问题之后，将问题规模缩小，然后调用自身来解决更小规模的问题。

下面将介绍三个经典的递归例子，并给出相应的代码实现。

1.阶乘计算：阶乘是指从1到给定的数字n之间所有整数的乘积。

它是递归问题的经典例子之一```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n - 1)```在阶乘的递归实现中，基本情况是n等于0时，返回1、递归调用是将问题规模变为n-1，然后将得到的结果与n相乘。

通过递归调用，可以一直计算到n为1，然后将每个阶乘结果逐步合并返回，最终得到n的阶乘。

2.斐波那契数列：斐波那契数列是指从0和1开始，后续的数字都是前两个数字之和。

```pythondef fib(n):if n <= 0:return 0elif n == 1:return 1else:return fib(n - 1) + fib(n - 2)```在斐波那契数列的递归实现中，基本情况是n小于等于0时返回0，n等于1时返回1、递归调用是将问题规模分为两个子问题，分别计算n-1和n-2的斐波那契数，然后将两个子问题的结果相加返回。

通过递归调用，可以一直计算到n为0或1，然后将每个斐波那契数逐步合并返回，最终得到第n个斐波那契数。

3.二叉树遍历：二叉树遍历是指按照一定的顺序访问二叉树的所有节点。

```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorderTraversal(root):if root is None:return []else:return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)```在二叉树的中序遍历的递归实现中，基本情况是判断当前节点是否为空，如果为空则返回一个空列表。

求int的上限与下限#include <stdio.h>//运行时间长,请等待.int main(){int min ,max;FILE *fin,*fout;fin=fopen("min of int.out","wb");fout=fopen("max of int.out","wb");for(min=-1;min<0;){min-- ;}fprintf(fin,"%d\n",min+1);for(max=1;max>0;){max++ ;}fprintf(fout,"%d\n",max-1);fclose(fin);fclose(fout);return 0;}1-1#include <stdio.h>int main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);double average;average=(a+b+c)/3.0; //一定要将int型转为浮点型printf("Average=%.3lf",average );system("pause");return 0;}1-2#include <stdio.h>int main(){double f,c;printf("请输入华氏温度f\n");scanf("%lf",&f);c=(f-32)*5/9 ;printf("摄氏温度c=%.3lf\n",c);return 0;}1-3#include <stdio.h>int main(){int n;scanf("%d",&n);printf("%d\n",(1+n)*n/2) ;system("pause");return 0;}1-4#include <stdio.h>#include <math.h>int main(){const double pi =4.0*atan(1.0);int n;scanf("%d",&n);while(n>=360){printf("请输入小于360°的角\n");scanf("%d",&n);}printf("正弦:%lf\n余弦:%lf",sin(n*pi/180),cos(n*pi/180));system("pause");return 0;}1-5#include <stdio.h>#include <math.h>int main(){double x1,y1,x2,y2;printf("请输入点A的坐标\n");scanf("%lf%lf",&x1,&y1);printf("请输入点B的坐标\n");scanf("%lf%lf",&x2,&y2);double d;d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));printf("%.3lf\n",d);return 0;}1-6#include <stdio.h>int main(){int a;scanf("%d",&a);if(a%2==0)printf("该数是偶数");else printf("该数非偶数");system("pause");return 0;}1-7#include <stdio.h>int main(){const int a=95;int n;printf("你要买多少件衣服\n");scanf("%d",&n);if(a*n>=300)printf("需要%.2lf元\n",a*n*0.85);else printf("需要%.2lf元\n",(double)a*n); //由于输出是小数%.2lf,故一定要将int型转化为浮点型system("pause");return 0;}1-8#include <stdio.h>#include <stdio.h>int main(){double a;scanf("%lf",&a);if(a>0)printf("%.2lf",a);else printf("%.2lf",-a);system("pause");return 0;}1-9(方法一)#include <stdio.h>int main(){int a,b,c,max,min,middle;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}min=a;if(a>b)min=b;if(a>c)min=c;max=a;if(a<b)max=b;if(a<c)max=c;middle=a+b+c-min-max;if(min+middle>max)printf("yes");else printf("no");system("pause");return 0;}1-9(方法二) #include <stdio.h>int main(){int a,b,c,t=0;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}if(b>c){t=b;b=c;c=t;}if(a+b>c)printf("yes");else printf("no");system("pause");return 0;}1-10#include <stdio.h>int main(){int n;scanf("%d",&n);if(n%4==0){if(n%100==0){if(n%400==0){printf("yes");}else printf("no");}else printf("yes");}else printf("no");system("pause");return 0;}3n+1解决篇1#include <stdio.h>int main(){int count=0;double i,m;scanf("%lf",&i);for(;i>1;){m=i/2;if(floor(m+0.5)!=m){i=3*i+1;i/=2;count+=2;}//floor(x)取x的整数部分.else {i/=2;count++;}}printf("%d\n",count);system("pause");return 0;}3n+1解决篇2#include<stdio.h>int main(){long long n, count = 0;//long long 的取值范围:-2^63~2^63-1scanf("%I64d", &n);while(n > 1) {if(n % 2 == 1) n = n*3+1;else n /= 2;count++;}printf("%I64d\n", count);return 0;}数据统计解决篇#include <stdio.h>int main(){int x,n=0,s=0,min,max;while(scanf("%d",&x)==1){if(n==0){min=max=x;}//读取第一个数的时候将第一个数赋值给min和max s+=x;if(x<min)min=x;if(x>max)max=x;n++;}printf("%d %d %.3lf\n",min,max,(double)s/n);system("pause");return 0;}2-1(fin)#include <stdio.h>int main(){FILE *fin,*fout;fin=fopen("digit.in","rb");fout=fopen("digit.out","wb");/*fin=stdin;fout=stdout;*/int a,i=0;fscanf(fin,"%d",&a);while(1){a/=10;i++;if(a<1)break;}fprintf(fout,"%d\r\n",i);fclose(fin);fclose(fout);//system("pause");return 0;}2-1(freopen)#include <stdio.h>//#define LOCAL//在编译选项中定义LOCALint main(){#ifdef LOCALfreopen("digit.in","r",stdin);freopen("digit.out","w",stdout);#endifint a,i=0;scanf("%d",&a);while(1){a/=10;i++;if(a<1)break;}printf("%d\n",i);return 0;}2-2(freopen)#include <stdio.h>//#define LOCAL//编译选项中定义int main(){#ifdef LOCALfreopen("daffodil.out","w",stdout);#endifint a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for (c=0;c<=9;c++){m=a*100+b*10+c;if(m==a*a*a+b*b*b+c*c*c)printf("%d\n",m);}}}//system("pause");return 0;}2-2(fin)#include <stdio.h>int main(){FILE *fout;fout=fopen("daffodil.out","wb");int a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for(c=0;c<=9;c++){m=a*a*a+b*b*b+c*c*c;if(m==a*100+b*10+c)fprintf(fout,"%d\r\n",m);}}}fclose(fout);return 0;}2-3(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("hanxin.in","rb");fout=fopen("hanxin.out","wb");//fin=stdin;//fout=stdout;int a,b,c,x,temp=0;//temp用来判断是否在10到100内存在这样的数fscanf(fin,"%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){fprintf(fout,"%d\r\n",x);temp=1;break;}}if(!temp)fprintf(fout,"No answer\r\n");fclose(fin);fclose(fout);return 0;}2-3(freopen)#include<stdio.h>{//会在编译选项中定义LOCAL#ifdef LOCALfreopen("hanxin.in","r",stdin);freopen("hanxin.out","w",stdout);#endifint a,b,c,x,temp=0;scanf("%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){printf("%d\n",x);temp=1;break;}}if(!temp)printf("No answer\n");return 0;}2-4(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("triangle.in","rb");fout=fopen("triangle.out","wb");//fin=stdin;//fout=stdout;int n,i,j,k;fscanf(fin,"%d\r\n",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)fprintf(fout," ");for(k=-2*i+2*n+1;k>=1;k--)fprintf(fout,"*");fprintf(fout,"\r\n");}fclose(fin);fclose(fout);return 0;}2-4(freopen)#include<stdio.h>{//在编译选项内定义LOCAL#ifdef LOCALfreopen("triangle.in","r",stdin);freopen("triangle.out","w",stdout);#endifint n,i,j,k;scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)printf(" ");for(k=2*n+1-2*i;k>=1;k--)printf("*");printf("\n");}return 0;}2-5(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("stat.in","rb");int n,a,i,m,count=0;fscanf(fin,"%d",&n);for(i=1;i<=n+1;i++){fscanf(fin,"%d",&a);if(i==n+1)m=a;}fclose(fin);fin=fopen("stat.in","rb");for(i=0;i<=n;i++){fscanf(fin,"%d",&a);if(i!=0){if(a<m)count++;}}fclose(fin);fout=fopen("stat.out","wb");fprintf(fout,"%d\r\n",count);fclose(fout);return 0;}2-5(freopen) #include<stdio.h>int main(){freopen("stat.in","r",stdin);freopen("stat.out","w",stdout);int n,a,i,m,count=0;scanf("%d",&n);for(i=1;i<=n+1;i++){scanf("%d",&a);if(i==n+1)m=a;}freopen("stat.in","r",stdin);for(i=0;i<=n;i++){scanf("%d",&a);if(i!=0){if(a<m)count++;}}printf("%d\n",count);return 0;}2-6(fin) #include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("harmony.in","rb");int n,i;double H=0;fscanf(fin,"%d",&n);for(i=1;i<=n;i++){H+=(double)1/i;}fclose(fin);fout=fopen("harmony.out","wb");fprintf(fout,"%.3lf\r\n",H);fclose(fout);return 0;}2-6(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("harmony.in","r",stdin);freopen("harmony.out","w",stdout);#endifint n,i;double H=0;scanf("%d",&n);for(i=1;i<=n;i++){H=H+double/i;}printf("%.3lf",H);return 0;}2-7(fin) #include<stdio.h>int main(){FILE *fout;int i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}fout=fopen("approximation.out","wb");fprintf(fout,"%lf\r\n",H);return 0;}2-7(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("approximation.in","r",stdin);freopen("approximation.out","w",stdout);#endifint i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}printf("%lf",H);return 0;}2-8(fin,double)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;double ii;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){ii=(double)i*i;H+=1/ii;}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC);//比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(fin,long long)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){long long ii=1;//定义ii=ii*i*i; //不用ii=i*i也不是ii*=i*i,这样做是为了防止i*i溢出; 可以认为这一步将int型转化为long long 型H+=1/(double)ii;//不是(double)1/ii}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC); ////比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(freopen)#include<stdio.h>#define LOCALint main(){#ifdef LOCALfreopen("subsequence.in","r",stdin);freopen("subsequence.out","w",stdout);#endifint n,m,i;double H=0,ii;scanf("%d%d",&n,&m);for(i=n;i<=m;i++){H+=1/((double)i*i);}printf("%.5lf\n",H);return 0;}2-9(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("decimal.in","rb");fout=fopen("decimal.out","wb");int a,b,c;fscanf(fin,"%d%d%d",&a,&b,&c);fprintf(fout,"%.*lf\r\n",c,(double)a/b);fclose(fin);fclose(fout);return 0;}2-9(freopen)#include<stdio.h>int main(){#ifdef LOCALfreopen("decimal.in","r",stdin);freopen("decimal.out","w",stdout);#endifint a,b,c;scanf("%d%d%d",&a,&b,&c);printf("%.*lf",c,(double)a/b);return 0;}2-10(全书看完再看这段代码) #include<cstdio>#include<algorithm>using namespace std;int main(){freopen("permutation.ans","w",stdout);int d[]={1,2,3,4,5,6,7,8,9};do{int a=d[0]*100+d[1]*10+d[2];int b=d[3]*100+d[4]*10+d[5];int c=d[6]*100+d[7]*10+d[8];if(c==3*a&&b==2*a)printf("%d %d %d\n",a,b,c);}while(next_permutation(d,d+9));return 0;}。

第二章信息的加工(算法及程序实现)一、算法的基本概念所谓算法就是对解题方法精确而完整的描述，由有限个步骤组成。

算法具有如下特征：有穷性、确定性、可行性、有0个或多个输入、有一个或多个输出。

1.有穷性。

一个算法必须保证它的执行步骤是有限的，即它是能终止的。

广义地说，“有穷性”一般指操作步骤的数量有限或能在合理的时间范围内完成全部操作。

2.确定性。

算法中的每个步骤必须有确切的含义，不能有二义性。

3.可行性。

算法中每一个步骤都要足够简单，是实际能做的，而且能在有限的时间内完成。

4.有0个或多个输入。

算法常需要对数据进行处理，一般需要从外界输入数据，如果所需的数据已经包含在算法中，则不再需要输入，此时是0个输入。

5.有一个或多个输出。

算法的目的是用来求解问题，问题求解的结果应以一定的方式输出，即必须告诉用户最后结果，因此至少要有一个输出。

二、算法的常用表示方法常用的算法表示方法有：自然语言、流程图、计算机语言等三种方法。

1.自然语言。

是指人们在日常生活中使用的语言，用自然语言描述的算法通俗易懂，但缺乏直观性和简洁性，容易产生歧义。

2.流程图。

是算法的一种图形化表示方法，与自然语言相比，它的描述更形象、更直观。

3.计算机语言。

是指编写程序的语言，它是计算机要执行的指令集合。

三、顺序、选择、循环三种控制结构算法的执行流程是指算法中各处理步骤的执行次序和模式，通常由以下三种基本结构组成：1.顺序结构是按照次序从上往下依次执行，每条语句必须而且只能执行一次。

2.选择结构，又称分支结构。

执行过程根据条件判断选择不同分支执行：条件为真时执行处理步骤stepl，否则执行处理步骤step2。

选择模式对条件是否成立只判断1次。

3.循环模式，是对某个条件进行判断，当结果为真时，执行步骤step(循环体)，然后再判断这个条件，当结果为真时，再次执行step，并继续判断条件。

重复上述过程，直到判断的结果为假，跳出循环，执行循环体后面的指令。

以下是C++中的一些经典题目及其算法解析：1. 两数之和（Two Sum）题目描述：给定一个整数数组nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

算法解析：可以使用哈希表来解决这个问题。

遍历数组，对于每个元素，计算目标和并减去当前元素，得到差值。

在哈希表中查找差值，如果存在则返回下标，否则将当前元素和下标存入哈希表。

2. 三数之和（3Sum）题目描述：给定一个包含n 个整数的数组nums，判断nums 中是否存在三个元素a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

算法解析：可以使用分治法来解决这个问题。

将数组分成A、B、C 三部分，分别求和并记录下标。

对于每个 A 的下标，分别判断 B 和 C 的部分是否存在和为-A 的数对，如果存在则返回结果。

3. 最长回文子串（Longest Palindromic Substring）题目描述：给定一个字符串s，找到s 中最长的回文子串。

你可以假设s 的最大长度为1000。

算法解析：可以使用动态规划来解决这个问题。

定义dp[i][j] 表示s[i..j] 是否为回文串。

根据回文串的性质，如果s[i] = s[j]，那么dp[i][j] 一定等于dp[i+1][j-1]。

因此，可以从字符串两端向中间遍历，每次判断两端字符是否相等，如果相等则更新dp 数组，最终找到最长的回文子串。

4. 二分查找（Binary Search）题目描述：给定一个有序数组nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

算法解析：可以使用二分查找来解决这个问题。

定义left 和right 指针指向数组的左右两端，每次比较中间元素和目标值的大小关系，根据比较结果更新左右指针的位置，直到找到目标值或者左右指针相遇。

如果找到了目标值，还需要判断左右指针指向的元素是否相同。

《经典算法-枚举与递归》作业设计方案（第一课时）一、作业目标本作业旨在通过实践操作，使学生能够：1. 理解枚举与递归的基本概念；2. 掌握简单的枚举与递归算法实现方法；3. 培养学生的逻辑思维能力和问题解决能力。

二、作业内容作业内容主要围绕枚举与递归算法展开，具体包括：1. 理论学习：学生需认真阅读教材中关于枚举与递归的章节，理解其基本概念、原理及适用场景。

2. 算法实践：学生需完成以下两个实践任务：（1）枚举法实践：设计一个程序，使用枚举法解决简单的数学问题，如求正整数的所有因数等。

要求学生在程序中明确标识出枚举的起始点和结束点，以及循环体中每次循环的逻辑。

（2）递归法实践：编写一个递归函数，实现简单的数学计算或逻辑判断功能。

例如，编写一个递归函数实现求阶乘或斐波那契数列等。

要求学生在程序中明确递归的基线条件和递归逻辑。

3. 程序编写：将理论学习和实践任务相结合，学生需自行设计一个小型项目，项目中至少包含一个枚举法和一个递归法的应用。

项目内容可自由选择，但需体现两种算法的特点和优势。

4. 代码调试：学生需对编写的程序进行调试，确保程序能够正确运行并得出预期结果。

在调试过程中，学生应学会使用基本的调试工具和方法，如打印输出、断点等。

三、作业要求1. 学生需在规定时间内完成作业，并保证作业的准确性和完整性。

2. 作业中的实践任务需有明确的算法思路和清晰的代码实现。

3. 在项目设计中，学生应注重算法的优化和创新，尽可能提高程序的运行效率和可读性。

4. 代码需规范书写，符合编程规范和语法要求。

四、作业评价1. 老师将根据学生作业的准确性、完整性和创新性进行评价。

2. 评价标准包括理论学习的理解程度、实践任务的完成情况以及项目设计的创意和优化程度。

3. 老师将对每位学生的作业进行详细批改，指出存在的问题和不足，并提供改进意见。

五、作业反馈1. 老师将通过课堂讲解、个别辅导等方式，对学生的作业进行反馈和指导。