大数算法与组合数学算法-ACM讲解.ppt
文本预览下载声明
大数运算与组合数学;問題;最簡單的方法;寫成電腦程式;那輸入呢?;void parse(char *s, int *a){
int i,j;
j=strlen(s);
for(i=0;ij;i++){
a[j-1-i]=s[0]-30;
}
}
void add(int *a, int *b, int *sum){
int i,c;
c=0;
for(i=0;i100;i++){
sum[i]=a[i]+b[i]+c;
if(sum[i]=10){
sum[i]=sum[i]-10;
c=1;
} else {
c=0;
}
}
};改進;減法? 乘法? 除法?;大數運算;大數運算;大整数的乘法;例子;例子;例子;例子;随机产生一个200位的数;乘法运算;比较两个数的大小;除法运算;除法运算（续）;组合数学研究对象;1。存在性问题;2。 计数问题;3。 构造性算法;4。 优化问题;组合问题的基本解题方法;2 通常与问题所涉及的组合数学概念无关的非常规方法。主要用于解那些需要独立思考见解独到和有所创新的问题。
数学归纳法
证明n个元素的集合，其子集恰为2n个
???一对应技术 将一个问题转化为另一种有常规算法的问题模式。例如，8“车”问题有多少个不同的安全状态。8个车处于安全状态当且仅当它们处于不同的8行和8列上。用一个排列a1，a2，…，a8，对应于一个安全状态，使ai表示第i行的ai列上放置一个车。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列的总数8！=40320。
;3 殊途同归方法;各区域顶点总数（包括重复计数）
角度1：;角度2：所有区域的内角和的总和的等式
两边同除以180度得
两式相减得区域总数;4 数论方法;回溯方法;N皇后问题;2 算符（operator）
算符是把问题的一个状态变换到另一个状态的方法代号。n皇后的一种摆法对应n个元素的排列方案（a1，a2，…,an）
必须满足条件：不产生对角线攻击和列攻击。
3。 结点（node）
用以表明某状态特征及关联方式的基本信息单元。结点的数据结构一般为记录类型。
Type node=record
operator : 算符类型；
state： 状态类型；
end;
Var stack：array[1。。maxdepth] of node；{节点数不超过maxdepth的一条路径}
or
Var
stack: array[1..20] of integer;
;当n＝4时，初始状态：空棋盘，
试放的顺序是从左至右，自上而下
（××××）;;求解n皇后问题，无非就是做两件事：
1。 从左至右逐条树枝地构造和检查解答树t；
2。检查t的节点是否对应问题的目标状态。为了加快检查速度，一般规定：
1。 在扩展一个分支节点前进行检查，如果它不满足约束条件，则不再构造以它为根节点的子树；
2。 已处理过的节点若以后不会再用，则不必保留，即回溯过程中经过的节点不再保留。 ;栈—重要的数据结构;算法框架;作为练习;从鸽笼原理到Ramsey理论;2 Ramsey问题和Ramsey数;Ramsey数;另一种表述;Ramsey数上界估计公式;上界估计程序;Procedure init; {输入ramsey数的两个参数}
Begin
clrscr;
repeat write(‘a=’);
readln(a);
until (a1) and (a=maxn);
repeat write(‘b=’);
readln(b);
until (b1) and (b=maxn);
end;;Procedure main
var I, j :integer;
Begin
for i:=2 to a do r[I,2]:=I; {建立递归边界}
for i:=2 to b do r[2,i]:=I;
for i:=3 to a do
for j:=3 to b do
if (odd(r[i-1,j]) or (odd(r[I,j-1])) then
r[I,j]:=r[i-1,j]+r[I,j-1]
显示全部