蟲食算

蟲食算

蟲食算是一種用字母或者說空格來代替數字的算式，由做題者復原算式。現在，我們一般稱其為“數字謎”或者說“數字謎題”。它對於開發智力具有一定的作用。

基本介紹

  • 中文名：蟲食算
  • 屬於：算式
  • 包含：用字母或者說空格來代替數字
  • 對於：開發智力具有一定的作用
出處,問題描述,輸入檔案,輸出檔案,樣例輸入,樣例輸出,數據規模,解題報告,代碼清單,

出處

NOIP2004提高組複賽最後一題：蟲食算。
蟲食算
(alpha.pas/dpr/c/cpp)

問題描述

所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據剩下的數字來判定被啃掉的字母。來看一個簡單的例子：
43#98650#45
+ 8468#6633
44445506978
其中#號代表被蟲子啃掉的數字。根據算式，我們很容易判斷：第一行的兩個數字分別是5和3，第二行的數字是5。
我們對問題做兩個限制：
首先，我們只考慮加法的蟲食算。這裡的加法是N進制加法，算式中三個數都有N位，允許有前導的0。
其次，蟲子把所有的數都啃光了，我們只知道哪些數字是相同的，我們將相同的數字用相同的字母表示，不同的數字用不同的字母表示。如果這個算式是N進制的，我們就取英文字母表午的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數字：但是這N個字母並不一定順序地代表0到N-1)。輸入數據保證N個字母分別至少出現一次。
BADC
+ CBDA
DCCC
上面的算式是一個4進制的算式。很顯然，我們只要讓ABCD分別代表0123，便可以讓這個式子成立了。你的任務是，對於給定的N進制加法算式，求出N個不同的字母分別代表的數字，使得該加法算式成立。輸入數據保證有且僅有一組解，

輸入檔案

輸入檔案包含4行。第一行有一個正整數N(N<=26)，後面的3行每行有一個由大寫字母組成的字元串，分別代表兩個加數以及和。這3個字元串左右兩端都沒有空格，從高位到低位，並且恰好有N位。

輸出檔案

輸出檔案alpha.out包含一行。在這一行中，應當包含唯一的那組解。解是這樣表示的：輸出N個數字，分別表示A，B，C……所代表的數字，相鄰的兩個數字用一個空格隔開，不能有多餘的空格。

樣例輸入

5
ABCED
BDACE
EBBAA

樣例輸出

1 0 3 4 2

數據規模

對於30%的數據，保證有N<=10；
對於50%的數據，保證有N<=15；
對於全部的數據，保證有N<=26。

解題報告

經典的搜尋題。最單純的搜尋的時間複雜度為O(n!)，是會非常嚴重的逾時的。計算機是很“笨”的，它不會思考，在盲目搜尋的過程中，很容易出現這種情況：
計算機在某一位搜尋出了一個算式1 + 1 = 3，並且繼續搜尋。
明顯，人眼很容易就看出這是不合法的，但計算機不會。於是，我們想到了第一個剪枝：每次搜尋的時候，從最後向前判斷是否有不合法的式子。
這一個剪枝非常簡單，但是效果卻非常的好。因為它剪去了很多不必要的搜尋。為了配合這一種剪枝更好的實行，搜尋順序的改變也成為大大提高程式效率的關鍵：從右往左，按照字母出現順序搜尋，有很大程度上提高了先剪掉廢枝的情況，使程式的效率得到大大的提高。
有了以上兩個剪枝，程式就已經可以通過大部分測試點了。但是有沒有更多的剪枝呢？答案是肯定的。
根據前面的剪枝，我們可以找到類似的幾個剪枝：
對於a + b = c的形式，假如：
A***?***
+ B*?**?**
C***???*
其中*代表已知，?代表未知。那么，A + B與C的情況並不能直接確定。但是，假如(A + B) % N與(A + B + 1) % N都不等於C的話，那么這個等式一定是不合法的。因為它只有進位和不進位的兩種情況。
同樣，我們在一個數組里記錄了Used表示一個數字有沒有用過，那么，對於某一位A + B = C的等式，如果已經得到了兩個數，另一個數還待搜尋的時候，我們還可以根據這個加入一個剪枝：
例如A + ? = C的形式，
考慮不進位的情況，則?處為P1 = (C - A + N) % N
假如考慮進位的情況，則?處為P2 = (C - A - 1 + N) % N
假如P1、P2均被使用過，那么這個搜尋一定是無效的，可以剪去。
有了以上的剪枝，就可以很輕鬆地通過所有的測試數據了。當然，還有很多值得思考的剪枝以及其他的思路，例如枚舉進位、解方程（但是可能需要枚舉）等，在這裡就不詳細討論了。

代碼清單

C++語言實現
#include <fstream>#include <string>using namespace std;ifstream    fin;ofstream    fout( "alpha.out" );bool        finish, hash[256], used[27];int        n, stk[27];string        a, b, c;string        word;void init(){    fin >> n >> a >> b >> c;    finish = false;}void outsol(){    int i, ans[27];    for ( i = 0; i < n; i++ )        ans[word - 65] = stk;    fout << ans[0];    for ( i = 1; i < n; i++ )        fout << " " << ans;    fout << endl;    finish = true;}void addup( char ch ){    if ( !hash[ch] )    {        hash[ch]    = true;        word        = word + ch;    }}string change( string str, char x, char y ){    for ( int i = 0; i < n; i++ )        if ( str == x )            str = y;    return(str);}void pre_doing(){    word = "";    memset( hash, 0, sizeof(hash) );    for ( int i = n - 1; i >= 0; i-- )    {        addup( a ); addup( b ); addup( c );    }    memset( used, 0, sizeof(used) );}bool bad(){    int p, g = 0;    for ( int i = n - 1; i >= 0; i-- )    {        if ( a >= n || b >= n || c >= n )            return(false);        p = a + b + g;        if ( p % n != c )            return(true);        g    = p / n;        p    %= n;    }    return(false);}bool modcheck(){    int i, p, p1, p2, g = 0;/* a + b = c, all know */    for ( i = n - 1; i >= 0; i-- )    {        if ( a >= n || b >= n || c >= n )            continue;        p = (a + b) % n;        if ( !(p == c || (p + 1) % n == c) )            return(true);    }/* a + ? = c */    for ( i = n - 1; i >= 0; i-- )    {        if ( !(a < n && c < n && b >= n) )            continue;        p1    = (c - a + n) % n;        p2    = (p1 - 1) % n;        if ( used[p1] && used[p2] )            return(true);    }/* ? + b = c */    for ( i = n - 1; i >= 0; i-- )    {        if ( !(a >= n && c < n && b < n) )            continue;        p1    = (c - b + n) % n;        p2    = (p1 - 1) % n;        if ( used[p1] && used[p2] )            return(true);    }/* a + b = ? */    for ( i = n - 1; i >= 0; i-- )    {        if ( !(a < n && b < n && c >= n) )            continue;        p1    = (a + b) % n;        p2    = (p1 + 1) % n;        if ( used[p1] && used[p2] )            return(true);    }    return(false);}void dfs( int l ){    int    i;    string    A, B, C;    if ( finish )        return;    if ( bad() )        return;    if ( modcheck() )        return;    if ( l == n )    {        outsol();        return;    }    for ( i = n - 1; i >= 0; i-- )        if ( !used )        {            used    = true; A = a; B = b; C = c;            a    = change( A, word[l], i );            b    = change( B, word[l], i );            c    = change( C, word[l], i );            stk[l]    = i;            dfs( l + 1 );            used = false; a = A; b = B; c = C;        }}int main(){    init();    pre_doing();    dfs( 0 );    return(0);}
pascal實現
var
a:Array[1..3,1..26]of char;
b:array['A'..'Z']of longint;
c:array[0..25]of boolean;
i,j,n:longint;
function check(x,m:longint):boolean;
var
yy:boolean;
i,j:longint;
begin
if ((b[a[1,x]]+b[a[2,x]]+m)mod n<>b[a[3,x]]) then exit(false);
for i:=1 to x-1 do
if (b[a[1,i]]<>-1)and(b[a[2,i]]<>-1)and(b[a[3,i]]<>-1)then
begin
yy:=true;
for j:=0 to 1 do
if (b[a[1,i]]+b[a[2,i]]+j)mod n=b[a[3,i]] then yy:=false;
if yy then exit(false);
end;
check:=true;
end;
procedure dfs(x,m:longint);
var i,j,d,p,mm:longint;
aa,bb,cc:boolean;
begin
if x=0 then begin
if m=0 then
begin
for i:=1 to n do write(b[chr(i+64)],' ');
close(input);close(output);
halt;
end;
exit;
end;
aa:=false;
bb:=false;
cc:=false;
if b[a[1,x]]<>-1 then aa:=true;
if b[a[2,x]]<>-1 then bb:=true;
if b[a[3,x]]<>-1 then cc:=true;
if (aa and bb and cc) then
begin
if check(x,m) then dfs(x-1,(m+b[a[1,x]]+b[a[2,x]])div n);
end
else if aa and bb then
begin
d:=(b[a[1,x]]+b[a[2,x]]+m)mod n;
if c[d] then
begin
b[a[3,x]]:=d;
c[d]:=false;
mm:=(b[a[1,x]]+b[a[2,x]]+m)div n;
if check(x,m) then dfs(x-1,mm);
c[d]:=true;
b[a[3,x]]:=-1;
end;
end
else if aa and cc then
begin
d:=(b[a[3,x]]-m-b[a[1,x]]+n)mod n;
if c[d] then
begin
b[a[2,x]]:=d;
c[d]:=false;
mm:=(d+b[a[1,x]]+m)div n;
if check(x,m) then dfs(x-1,mm);
m:=mm;
c[d]:=true;
b[a[2,x]]:=-1;
end;
end
else if bb and cc then
begin
d:=(b[a[3,x]]-m-b[a[2,x]]+n)mod n;
if c[d] then
begin
b[a[1,x]]:=d;
c[d]:=false;
mm:=(d+b[a[2,x]]+m)div n;
if check(x,m) then dfs(x-1,mm);
m:=mm;
c[d]:=true;
b[a[1,x]]:=-1;
end;
end
else if (not aa)and(not bb)and(not cc) then
begin
if a[1,x]<>a[2,x] then
begin
for i:=n-1 downto 0 do
for j:=n-1 downto 0 do
if (c[i] and c[j])and(i<>j) then
begin
c[i]:=false;
c[j]:=false;
b[a[1,x]]:=j;
b[a[2,x]]:=i;
dfs(x,m);
c[i]:=true;
c[j]:=true;
b[a[1,x]]:=-1;
b[a[2,x]]:=-1;
end;
end
else
for i:=n-1 downto 0 do
if c[i] then
begin
b[a[1,x]]:=i;
c[i]:=false;
dfs(x,m);
b[a[p,x]]:=-1;
c[i]:=true;
end;
end
else begin
for i:=n-1 downto 0 do
if c[i] then
begin
if not aa then p:=1
else if not bb then p:=2
else if not cc then p:=3;
b[a[p,x]]:=i;
c[i]:=false;
dfs(x,m);
b[a[p,x]]:=-1;
c[i]:=true;
end;
end;
end;
begin
readln(n);
for i:=1 to 3 do
begin
for j:=1 to n do
read(a[i,j]);
readln;
end;
fillchar(b,sizeof(b),255);
fillchar(c,sizeof(c),true);
dfs(n,0);
end.
總結
搜尋題的框架往往不難找到，關鍵就是在搜尋的最佳化上，本文的主要篇幅也就是討論了幾種有效的最佳化。搜尋問題的最佳化更多的需要選手的經驗和思考、分析問題的能力，所以搜尋剪枝也是競賽中經久不衰的經典問題。

相關詞條

熱門詞條

聯絡我們