发布时间 : 星期六 文章Noip常用算法大全更新完毕开始阅读
End;
Writeln(f[M]); End.
C.求恰好装满的情况数。 Ahoi2001 Problem2
求自然数n本质不同的质数和的表达式的数目。
思路一，生成每个质数的系数的排列，在一一测试，这是通法。 procedure try(dep:integer); var i,j:integer; begin
cal; {此过程计算当前系数的计算结果，now为结果} if now>n then exit; {剪枝}
if dep=l+1 then begin {生成所有系数} cal;
if now=n then inc(tot); exit; end;
for i:=0 to n div pr[dep] do begin xs[dep]:=i; try(dep+1); xs[dep]:=0; end; end;
思路二，递归搜索效率较高 procedure try(dep,rest:integer); var i,j,x:integer; begin
if (rest<=0) or (dep=l+1) then begin if rest=0 then inc(tot); exit; end;
for i:=0 to rest div pr[dep] do try(dep+1,rest-pr[dep]*i); end;
{main: try(1,n); }
思路三：可使用动态规划求解 USACO1.2 money system
V个物品，背包容量为n，求放法总数。 转移方程：
Procedure update; var j,k:integer; begin c:=a;
for j:=0 to n do if a[j]>0 then
for k:=1 to n div now do
if j+now*k<=n then inc(c[j+now*k],a[j]); a:=c; end; {main} begin
read(now); {读入第一个物品的重量}
i:=0; {a为背包容量为i时的放法总数} while i<=n do begin
a:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1，作为初值} for i:=2 to v do begin
read(now);
update; {动态更新} end;
writeln(a[n]);
四、排序算法 1.快速排序：
procedure qsort(l,r:integer); var i,j,mid:integer; begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat
while a[i]
if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i);dec(j); {继续找} end; until i>j;
if l B.插入排序： 思路：当前a[1]..a[i-1]已排好序了，现要插入a使a[1]..a有序。 procedure insert_sort; var i,j:integer; begin for i:=2 to n do begin a[0]:=a; j:=i-1; while a[0] a[j+1]:=a[0]; end; end;{inset_sort} C.选择排序： procedure sort; var i,j,k:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if a>a[j] then swap(a,a[j]); end; D. 冒泡排序 procedure bubble_sort; var i,j,k:integer; begin for i:=1 to n-1 do for j:=n downto i+1 do if a[j] E.堆排序： procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数} var k:integer; begin a[0]:=a; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1} while k<=m do begin if (k a:=a[0]; {将根放在合适的位置} end; procedure heapsort; var j:integer; begin for j:=n div 2 downto 1 do sift(j,n); for j:=n downto 2 do begin swap(a[1],a[j]); sift(1,j-1); end; end; F. 归并排序 {a为序列表，tmp为辅助数组} procedure merge(var a:listtype; p,q,r:integer); {将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]} var I,j,t:integer; tmp:listtype; begin t:=p;i:=p;j:=q+1;{t为tmp指针，I,j分别为左右子序列的指针} while (t<=r) do begin if (i<=q){左序列有剩余} and ((j>r) or (a<=a[j])) {满足取左边序列当前元素的要求} then begin tmp[t]:=a; inc(i); end else begin tmp[t]:=a[j];inc(j); end; inc(t); end; for i:=p to r do a:=tmp; end;{merge} procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]} var q:integer; begin if p<>r then begin q:=(p+r-1) div 2; merge_sort (a,p,q); merge_sort (a,q+1,r); merge (a,p,q,r); end; end; {main} begin