算法合集之由圖論問題淺析算法優(yōu)化-資料下載頁(yè)
2025-06-10 01:33本頁(yè)面
【正文】 exact number of spots on each cow in the subgroup of troublemakers. He can, however, remember which cows in the group have the same number of spots, and which of any pair of cows has more spots (if the spot counts differ). He describes such a pattern with a sequence of K ranks in the range 1..S. For example, consider this sequence: 1 4 4 3 2 1In this example, FJ is seeking a consecutive sequence of 6 cows from among his N cows in a line. Cows 1 and 6 in this sequence have the same number of spots (although this number is not necessarily 1) and they have the smallest number of spots of cows 1..6 (since they are labeled as 39。139。). Cow 5 has the secondsmallest number of spots, different from all the other cows 1..6. Cows 2 and 3 have the same number of spots, and this number is the largest of all cows 1..6.If the true count of spots for some sequence of cows is: 5 6 2 10 10 7 3 2 9then only the subsequence 2 10 10 7 3 2 matches FJ39。s pattern above.Please help FJ locate all the lengthK subsequences in his line of cows that match his specified pattern.PROBLEM NAME: cpatternINPUT FORMAT:* Line 1: Three spaceseparated integers: N, K, and S* Lines 2..N+1: Line i+1 describes the number of spots on cow i.* Lines N+2..N+K+1: Line i+N+1 describes patternrank slot i.SAMPLE INPUT (file ):9 6 1056210107329144321INPUT DETAILS:The sample input corresponds to the example given in the problem statement.OUTPUT FORMAT:* Line 1: The number of indices, B, at which the pattern matches* Lines 2..B+1: An index (in the range 1..N) of the starting location where the pattern matches.SAMPLE OUTPUT (file ):13OUTPUT DETAILS:There is only one match, at position 3 within FJ39。s sequence of N cows.二、代碼 《Fishing Net》的分析中最后一個(gè)算法的Pascal實(shí)現(xiàn)：program net。const maxn = 1100。 maxm = 1000000。 rantimes = 5。var net: array [1..maxn,1..maxn] of longint。 deg: array [1..maxn] of longint。 map: array [1..maxn,1..maxn] of boolean。 n, m: longint。procedure ReadIn()。var i, a, b: longint。begin fillchar(deg,sizeof(deg),0)。 fillchar(map,sizeof(map),0)。 for i:=1 to m do begin read(a,b)。 inc(deg[a])。 net[a,deg[a]]:=b。 map[a,b]:=true。 inc(deg[b])。 net[b,deg[b]]:=a。 map[b,a]:=true。 end。end。procedure RandomSwap()。var i, j, loca, locb, t: longint。begin for i:=1 to n do if (deg[i]1) then begin loca:=1。 t:=net[i,loca]。 for j:=1 to deg[i] do begin locb:=random(deg[i])+1。 net[i,loca]:=net[i,locb]。 loca:=locb。 end。 net[i,loca]:=t。 end。end。var dis: array [0..maxn,0..maxn] of longint。 vis: array [1..maxn] of boolean。 row: array [1..maxn] of longint。function Search(dep,a:longint): boolean。var i, b: longint。begin result:=false。 vis[a]:=true。 row[dep]:=a。 b:=0。 for i:=dep1 downto 1 do begin dis[a,row[i]]:=1+dis[b,row[i]]。 if map[a,row[i]] then begin if dis[a,row[i]]2 then exit。 dis[a,row[i]]:=1。 b:=row[i]。 end。 end。 for i:=1 to deg[a] do if (not vis[net[a,i]]) then if (not Search(dep+1,net[a,i])) then exit。 result:=true。end。function MaybePerfect(): boolean。var i: longint。begin fillchar(dis,sizeof(dis),0)。 fillchar(vis,sizeof(vis),0)。 fillchar(row,sizeof(row),0)。 result:=false。 for i:=1 to n do if (not vis[i]) then if (not Search(1,i)) then exit。 result:=true。end。procedure Solve()。 var perfect: boolean。 i: longint。begin ReadIn。 perfect:=true。 for i:=1 to rantimes do begin if (not MaybePerfect) then begin perfect:=false。 break。 end。 RandomSwap。 end。 if perfect then writeln(39。Perfect39。) else writeln(39。Imperfect39。)。 writeln。end。begin assignfile(input,39。39。)。 reset(input)。 assignfile(output,39。39。)。 rewrite(output)。 repeat read(n,m)。 if (n0) then Solve。 until (n=0)。 closefile(input)。 closefile(output)。end.在線代理|網(wǎng)頁(yè)代理|代理網(wǎng)頁(yè)| 減肥藥排行榜|淘寶最好的減肥藥|什么減肥藥效果最好|減肥瘦身藥
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1