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]mid do dec(j);{在右半部分寻找比中间数小的数}

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