程序设计,数据结构,算法
bensenoier的快乐天堂
vijos 1128选数!!!——经典的深搜算法,记住!!!!2009-06-29 14:54描述 Description
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
输入格式 Input Format
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000
输出格式 Output Format
一个整数(满足条件的种数)。
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
program ll;
var
s,zong,m,p,k,n,i:longint;
a:array[0..100000] of longint;
function pan(q:longint):boolean;
var
j:integer;
begin
for j:=2 to trunc(sqrt(q)) do
if q mod j = 0 then exit(false); /////////判断素数!!!!
exit(true);
end;
procedure run(x:longint); ////////////////////这里的x表示总的量,x最大是n,含义是从n个数中一一寻
begin ///////////////////找,if 当前找到的第x个数大于n,则是边界,跳出!!!!
if x>n then exit
else
begin
s:=s+a[x];
inc(m);
if m<k then run(x+1)
else
if pan(s) then inc(zong); /////////////这里是深搜的经典算法,因为从一到n选数,
s:=s-a[x]; //////////当前状态只有两种选择,一是选这个数,二是不选!!
dec(m);
run(x+1);
end;
end;
begin
readln(n,k);
for i:=1 to n do
read(a[i]);
zong:=0;m:=0;s:=0;
run(1);
writeln(zong);
end.
这种深搜做法很棒,就是从第一个到最后一个,如果用循环也可以!!!!!!
搜索方法小结 (算法原码吧)
2008-05-21 19:38文章由 算法源码吧(doc.guandang.net)收集
不管哪种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解(可行解),搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解,我们用两张表来进行搜索,一个叫OPEN表,表示那些已经展开但还没有访问的结点集,另一个叫CLOSE表,表示那些已经访问的结点集。
一、蛮力搜索(DFS,BFS)
DFS和BFS是最基本的搜索算法,用上面的形式表示它们是非常相似的。
BFS(Breadth-First-Search 宽度优先搜索)
{深搜全排列} program qpl(input,output); uses crt; label ss ,hs; var a,fx,b:array [1..30] of integer; {a 数组存每一步搜索到的字母,fx 数据...
深搜广搜遍历算法_计算机软件及应用_IT/计算机_专业资料。信息学资料——算法 ... 经典的深搜算法 暂无评价 11页 免费 图的深度优先搜索遍历算... 6页 免费...
ACM 竞赛经典算法 计算机与信息技术学院 目 录 第四次课 深度搜索 ......第五次课深搜 2 1、n2 的棋盘,填 1~n2 个数,要求下比上大,左比右大。程序...
图论中的常用经典算法_IT/计算机_专业资料。Jsoi2006 春季函授 A 层次讲义(3...实际上我们知道,递归(深搜)之类的算法一般用于求所有解问题(例如求从 A 出发...
搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库...而搜索技术的核心是 搜索算法,而所有的搜索算法的优化主要是在经典的搜索算法上...
经典查找算法_IT/计算机_专业资料。各种常用查找算法的比较查找1.线性查找 int...的话要么找了一遍了已经存在这个数了 printf("error"); } 2 (2)二次探查...
ACM经典算法_电脑基础知识_IT/计算机_专业资料。关于排列,组合,深搜的一些实际问题!ACM 竞赛经典算法 竞赛经典算法第一课递归一、pascal 特点: 1. 编写程序结构...
深搜优化——缩小搜索范围 缩小搜索范围——邮票面额 深搜优化 缩小搜索范围 邮票面额 算法基本框架(1)面额为1的邮票是必需的,可以固定。 (2)增加一种面额并把...
广搜经典算法_计算机软件及应用_IT/计算机_专业资料。广度搜索经典算法代码Type yu=record e,f:longint; end; Var n,k,m,i,h,t,j,c:longint; a:array[...
图论中的常用经典算法第一节一、生成树的概念若图是连通的无向图或强连通的有...实际上我们知道,递归(深搜)之类的算法一般用于求所有解问题(例如求从 A 出发...
热门文档