营销型网站的盈利模式,外发加工合同协议书,北京丰台做网站,比较好的网站开发公司chapter1 算法问题求解基础
1.1算法概述
1.什么是算法
算法—用计算机实现的问题求解方法。5个特征 #xff08;1#xff09;输入#xff1a;0或多个 #xff08;2#xff09;输出#xff1a;至少一个 #xff08;3#xff09;确定性#xff1a;算法每一条指令都有…chapter1 算法问题求解基础
1.1算法概述
1.什么是算法
算法—用计算机实现的问题求解方法。5个特征 1输入0或多个 2输出至少一个 3确定性算法每一条指令都有明确的定义 4能行性算法每一条指令必须足够基本可以用已实现的基本运算执行有限次来实现。 5有穷性有限步骤后终止描述方法 大白话、流程图、伪代码、程序设计语言 例1 计算两个整数的最大公约数辗转相除法欧几里得算法、连续整数检测算法 用于计算两个整数m和n0mn)的最大公约数gcd(m,n).其计算过程是重复下列等式直到n mod m0. gcd(m,n)gcd(n mod m,m) 例如gcd(2460)gcd(12,24)gcd(0,12)12 程序1-1 欧几里得递归算法 (递归调用函数)
#includeiostream
#includealgorithm
using namespace std;//欧几里得递归算法void Swap(int a,int b)//用于交换两个数的函数其实有内置的swap函数注意要变量的引用
{int ca;ab;bc;
}
int RGcd(int m,int n)//0mn
{if(m0)return n;return RGcd(n%m,m);
}
int Gcd(int m,int n)
{if(mn)Swap(m,n);return RGcd(m,n);
}
int main()
{int m,n;cinmn;coutGcd(m,n);return 0;}
程序1-2 欧几里得迭代算法(循环
#includebits/stdc.h
using namespace std;int Gcd(int m,int n)
{if(m0)return n;if(n0)return m;if(mn)swap(m,n);//n中保存大的数while(m0){int remn%m;nm;mrem;}return n;
}
int main()
{int m,n;cinmn;coutGcd(m,n);return 0;}连续整数检测算法 最大公约数定义能够同时整除它们的最大正整数。因此最大公约数小于或等于两数中的较小者。tmin{m,n},然后检查t能否整除m和n ,若能即为解否则t–继续检测
#includebits/stdc.h
using namespace std;int Gcd(int m,int n)
{if(m0)return n;if(n0)return m;int tmn?n:m;while(m%t ||n%t)t--;return t;
}
int main()
{int m,n;cinmn;coutGcd(m,n);return 0;}
2.为什么学习算法
重要重要重要 一个受过良好的计算机科学知识训练的人知道如何处理算法即构造算法、操纵算法、理解算法和分析算法。算法远不只是为了编写好的计算程序它是一种具有一般意义的智能工具必定有助于对其他学科的理解。
1.2 问题求解方法
软件开发的过程----使用计算机求解问题的过程。 计算机解题的核心任务----设计算法
1.问题和问题求解
问题----与希望的目标不一致
2.问题求解过程
理解问题设计方案
何处着手类似问题一些特殊示例进行分析
实现方案回顾复查
评估改进、简化和推广
3.系统生命周期
系统生命周期软件工程将软件开发和维护过程分成若干阶段。分析做什么、设计如何做、编码、测试和维护
1.3 算法设计和分析
1.算法问题求解过程
精确算法、启发式算法可能更有效但未必是最优解
2.如何设计算法
学习基本算法。 如合并排序和快速排序都可以视为分治法产生的排序算法但二者是不同的算法。
3.如何表示算法
自然语言、流程图、伪代码、程序设计语言等下面主要用c/c来描述
4.如何确认算法
算法确认对于所有的合法术后如都能在有限时间输出预期结果。 算法证明使用数学方法
5.如何分析算法
执行时间和所需空间
1.4 递归和归纳
重复性计算 1递归 2迭代 归纳法和递归关系密切可以用归纳法证明递归算法的正确性。
1.递归
递归定义直接或间接引用自身的定义方法。包括基础情况和递归部分 例1-1 斐波那契数列 F00,F11; FnFn-1Fn-2; 需要注意的是递归实现的斐波那契数列在计算过程中会存在大量的重复计算效率较低。如果需要计算较大的斐波那契数列建议使用迭代或动态规划的方法可以避免重复计算提高效率。
long Fib(int n)
{if(n1)return n;else return Fib(n-1)Fib(n-2);
}2.递归算法示例 例1-2 逆序输出整数的各位数 设有正整数n12345,现希望逆序输出54321. 设k位整数为d1d2…dk,要得到dkdk-1…d1可以分两步 1首先输出dk 2然后输出由前k-1位组成的正整数d1d2…dk-1 得到下面的递归程序
#includebits/stdc.h
using namespace std;void PrintDigit(unsigned int n)
{coutn%10;if(n10)PrintDigit(n/10);
}
int main()
{unsigned int n;cinn;PrintDigit(n);return 0;
} 例1-3 汉诺塔问题 假定有三个塔座x,y,z,在塔座上有n个直径不同的圆盘它们按直径大小从小到大编号为12…n。现要求将x塔座上的n个圆盘移动到y上并按相同的顺序叠排。移动时 1每次只能移动一个圆盘 2圆盘可以加到塔座x、y、z中任意一个之上 3任何时刻都不能将一个较大的圆盘放在较小的圆盘之上 假定圆盘从小到大编号为1-n移动圆盘的算法可以粗略地描述如下 1以y为中介将前n-1个圆盘从x移到z上 2将第n个圆盘移到y上 3以x为中介将z上的n-1个圆盘移到y上
#includebits/stdc.h
using namespace std;
enum tower{AX,BY,CZ};
void Move(int n,tower x,tower y)
{//将第n个圆盘从x移到y的顶部coutThe disk n is moved from char(x) to top of tower char(y)endl;
}
void Hanoi(int n,tower x,tower y,tower z)//将n个圆盘从x-y,z作为中介
{if(n){Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);}
}
int main()
{Hanoi(3,A,B,C);return 0;}输出如下
The disk 1 is moved from X to top of tower Y
The disk 2 is moved from X to top of tower Z
The disk 1 is moved from Y to top of tower Z
The disk 3 is moved from X to top of tower Y
The disk 1 is moved from Z to top of tower X
The disk 2 is moved from Z to top of tower Y
The disk 1 is moved from X to top of tower Y例1-4 产生各种可能的排列 给定n个自然数{012…n-1}的集合。设计一个算法输出该集合所有可能的排列permutation).n个自然数的集合有n!个不同的排列。 介绍一种求此问题的简单递归算法。 由四个自然数组成的排列通过以下方式构造: 1以0 开头紧随其后为{123}的各种排列 2以1 开头紧随其后为{023}的各种排列 3以2 开头紧随其后为{013}的各种排列 4以3 开头紧随其后为{012}的各种排列 语句1中“紧随其后为{123}的各种排列”实质上是求比原始问题少一个数的排列生成问题。相当于原题目这是一个同类子问题但规模小一些。意味着可用递归求解 template class Tvoid Perm(T a[],int k,int n)
{if(kn-1){for(int i0;in;i)//输出一种排列couta[i] ;}elsefor(int ik;in;i){T ta[k];a[k]a[i];a[i]t;//产生{a[k],...a[n-1]}各种排列Perm(a,k1,n);ta[k];a[k]a[i];s[i]t;//产生{a[k1],...a[n-1]}各种排列}
}
本章小结
递归是强有力的算法算法结构。
习题 1.写一个递归算法和一个迭代算法计算二项式系数。 CnmCn-1mCn-1m-1n!/m!(n-m)! 递归法
#includebits/stdc.h
using namespace std;
int Combine(int m,int n)
{if(m0||mn)return 1;//注意递归出口是一个确定的值else return Combine(m,n-1)Combine(m-1,n-1);
}int main()
{int m,n;cinmn;coutCombine(m,n);return 0;}
迭代法是不是用一个数组保存结果呀然后依次计算。 2.S是有n个元素的集合S的幂集是S的所有可能的子集组成的集合。例如S{a,b,c},S的幂集{{}{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.写一个递归函数以S为输入输出S的幂集。
