全国

热门城市 | 全国 北京 上海 广东

华北地区 | 北京 天津 河北 山西 内蒙古

东北地区 | 辽宁 吉林 黑龙江

华东地区 | 上海 江苏 浙江 安徽 福建 江西 山东

华中地区 | 河南 湖北 湖南

西南地区 | 重庆 四川 贵州 云南 西藏

西北地区 | 陕西 甘肃 青海 宁夏 新疆

华南地区 | 广东 广西 海南

  • 微 信
    高考

    关注高考网公众号

    (www_gaokao_com)
    了解更多高考资讯

首页 > 高中频道 > 信息学联赛知识 > 信息学联赛知识:贪心策略的特点与在信息学竞赛中的应用

信息学联赛知识:贪心策略的特点与在信息学竞赛中的应用

2009-11-12 23:06:59网络

  贪心策略的特点与在信息学竞赛中的应用

  1、求最长路径问题(NOI93):

  对一个不存在回路的有向图,编程求出途经结点数最多的一条路径。有向图存放在一个文本文件中,第0行为一个数字,为该图的结点总数N,其下还有N行,每行有N个非0即1的数字。若第i行第j列的数字为1,则表示结点i到结点j存在由i指向j的边,否则该数为0。

  2、删数问题的源程序:

  输入数据:一个高精度正整数N,所删除的数字个数S。

  输出数据:去掉的数字的位置和组成的新的正整数。

  Program Delete_digit;

  Var n:string;{n是由键盘输入的高精度正整数}

  s,a,b,c:byte;{s是所要删除的数字的个数}

  data:array[1..200] of 0..9; {记录删除的数字所在位置}

  begin

  readln(n);

  readln(s);

  for a:=1 to s do

  for b:=1 to length(n) do if n[b]>n[b+1] then {贪心选择}

  begin

  delete(n,b,1);

  data[a]:=b+a-1; {记录所删除的数字的位置}

  break;

  end;

  while n[1]='0' do delete(n,1,1); {将字符串首的若干个"0"去掉}

  writeln(n);

  for a:=1 to s do writeln(data[a],' ');

  end.

  3、最优乘车问题

  输入数据:输入文件INPUT.TXT。文件的第行是一个数字M(1≤M≤100)表示开通了M条单向巴士线路,第2行是一个数字N(1<N≤500),表示共有N个车站。从第3行到第M+2行依次给出了第一条到第M条巴士线路的信息。其中第i+2行给出的是第i条巴士线路的信息,从左至右依次按行行驶顺序给出了该线路上的所有站点,相邻两个站号之间用一个空格隔开。

  输出数据:输出文件是OUTPUT.TXT。文件只有一行,为最少换车次数(在0,1,…,M-1中取值),0表示不需换车即可达到。如果无法乘车达到S公园,则输出"NO"。

  Program Travel;

  var m:1..100; {m为开通的单向巴士线路数}

  n:1..500; {n为车站总数}

  result:array[1..501] of -1..100; {到某车站的最少换车数}

  num:array[1..500,1..50] of 1..500; {从某车站可达的所有车站序列}

  sum:array[1..500] of 0..50; {从某车站可达的车站总数}

  check:array[1..500] of Boolean; {某车站是否已扩展完}

  Procedure Init;

  var f1:text;

  a,b,c,d:byte;

  data:array[1..100] of 0..100;

  begin

  assign(f1,'input.txt');

  reset(f1);

  readln(f1,m);

  readln(f1,n);

  result[501]:=100;

  for a:=1 to m do

  begin

  for b:=1 to 100 do data[b]:=0;

  b:=0;

  repeat

  inc(b);

  read(f1,data[b]);

  until eoln(f1);

  for c:=1 to b-1 do

  for d:=c+1 to b do

  begin

  inc(sum[data[c]]);

  num[data[c],sum[data[c]]]:=data[d];

  end;

  end;

  end;

  Procedure Done;

  var min,a,b,c,total:integer;

  begin

  fillchar(result,sizeof(result),-1);

  result[1]:=0;

  for c:=1 to sum[1] do result[num[1,c]]:=0;

  b:=data[1,1];

  repeat

  for c:=1 to sum[b] do

  if (result[num[b,c]]=-1) then result[num[b,c]]:=result[b]+1;

  min:=501;

  for c:=1 to n do if (result[c]<>-1) and (result[c]<result[min])

  then min:=c;

  b:=min;

  until result[n]<>-1;

  writeln(result[n]);{到达S公园的最少换车次数}

  end;

  begin

  Init;

  end.

  4、最佳游览路线问题

  输入数据:输入文件是INPUT.TXT。文件的第一行是两个整数M和N,之间用一个空格符隔开,M表示有多少条旅游街(1≤M≤100),N表示有多少条林荫道(1≤N≤20000)。接下里的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数,依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。

  输出文件:输出文件是 OUTPUT.TXT。文件只有一行,是一个整数,表示你的程序找到的最佳浏览路线的总分值。

  Program Tour;

  var m,n:integer; {M为旅游街数,N为林荫道数}

  data:array[1..20000] of -100..100;{data是由相邻两条林荫道所分}

  procedure Init; {隔的旅游街的最大分值}

  var a,b,c:integer;

  f1:text;

  begin

  assign(f1,'input.txt');

  reset(f1);

  read(f1,m,n);

  for a:=1 to n-1 do read(f1,data[a]); {读取每一段旅游街的分值}

  for a:=2 to m do

  for b:=1 to n-1 do

  begin

  read(f1,c);

  if c>data[b] then data[b]:=c; {读取每一段旅游街的分值,并选择}

  end; {到目前位置所在列的最大分值记入数组data}

  close(f1);

  end;

  procedure Done;

  var a,sum,result,c:integer;

  f2:text;

  begin

  result:=0;

  sum:=0;

  a:=0;

  while (a<n) do

  begin

  inc(a); {从数组的第一个数据开始累加,将累加所}

  sum:=sum+data[a]; {得到的最大分值记入result}

  if sum>result then result:=sum;

  if sum<0 then sum:=0; {若当前累加值为负数,则从当前状态起从新}

  end; {累加}

  assign(f2,'output.txt');

  rewrite(f2);

  writeln(f2,result);

  close(f2);

  end;

  begin

  Init;

  Done;

  end.

 

[标签:竞赛联赛 竞赛]

分享:

高考院校库(挑大学·选专业,一步到位!)

高考院校库(挑大学·选专业,一步到位!)

高校分数线

专业分数线

  • 欢迎扫描二维码
    关注高考网微信
    ID:gaokao_com

  • 👇扫描免费领
    近十年高考真题汇总
    备考、选科和专业解读
    关注高考网官方服务号