分析midea0978的《一個C#算法分析求解》（三）（完）
六、逆算準備
根據J和K的關系，很容易就可以根據數組個數計算出實際字符個數。
建立相應的字符對象數組，并使用密碼表中不存在的字符（這里是空格符）初始化。
為Bts屬性指定一個和原數組個數一樣的全0數組，用于存放結果，
而Bts2中放置原數組。因此，我們所要做的事情就是，對于這個字符對象數組中的每一個對象，
找到一個合適的N，使得Bts中的數據和Bts2一樣。這個時候每個字符對象對應的字符就是密碼表中的第N個字符。
ReCalc中建立了一個列表數組lists，用于存放每個字節受哪些字符對象“控制”（由該字符對象參數生成）。
七、開始逆算
準備好上面的工作后，就可以開始逆算了。
對于字節數組中start位置的字節，它的控制列表為list=lists[start]，
也就是說，所有影響這個位置的字節碼生成的字符對象ID，都存放在這個list中。
我們只需要遍歷這個list中每一個字符對象的所有NList可能，就可以計算出所有Bts[start]的可能，
取其中Bts[start]=Bts2[start]的就是了。
因為J的關系，list中最大的元素個數是3，所以，最多只需要3層循環。
此外，還有一個技巧需要說明，最后一個字節的控制列表只有一個字符對象，并且一定是最后的那個，這些從
J和K那里可以得知。
每一次NList的循環之前，都需要先備份K和M處的字節數據，以備下一輪循環前還原。
循環把NList的每一個N可能賦值給這個字符對象的N，然后執行Cal計算字節數據。
循環內部再嵌套控制列表list中的下一個字符對象。
在最里面一層循環里面，對比Bts[start]是否等于Bts2[start]，
如果相等，表明該層控制列表各字符對象的N值符合要求（但不是唯一的可能，還可能有別的組合）。
此時，就可以進入start－1層的計算了，該是遞歸上場的時候了。
且慢，在這之前，還需要做一些準備工作。
這一層已經計算好的字符對象，在下一層的時候可不能重新參與計算，否則就會影響這一層已經計算好的值了。
根據遞歸原則，我們應該“鎖定”這些對象，不允許子遞歸修改這些對象，
子遞歸只能通過循環控制列表中的其它對象來“湊”出一個合適的Bts(start)。
八、總結
整個遞歸算法是深度搜索算法。由于字符與字符之前有相互關系，所以必須是深度搜索，
但又因為這個關系只存在相鄰字符之間，所以深度搜索不必每次“到底”。
運算速度還不錯，所以就不做性能優化了。
歷時24小時左右（20＋4，中間小睡了一會）
大石頭
QQ:99363590
Email:gxuhy#21cn.com
http://www.nnhy.org
2007-12-02 01:04
C#逆向算法分析
2
/// <summary>
3
/// 搜索4
/// </summary>5
/// <param name="ts"></param>6
/// <param name="lists"></param>7
/// <param name="start"></param>8
/// <returns></returns>9
public static Boolean Find(CharObject[] ts, List<Int32> locks, List<Int32>[] lists, Int32 start)10
{
11
Console.WriteLine(new String(' ', 12 - start) + "第{0}層", start.ToString());12
13
//結束條件14
if (start < 0)15
{
16
StringBuilder sb = new StringBuilder();17
for (int i = 0; i < ts.Length; i++)18
{19
if (ts[i] == null) break;20
sb.Append(ts[i].C);21
}22
Console.WriteLine(sb.ToString());23
//如果需要取得所有結果，只需要把下面改成return false;24
//return false;25
return true;26
}27
28
//遞歸過程29
List<Int32> list = new List<int>();30
//排除鎖定項31
foreach (Int32 t in lists[start])32
{33
if (!locks.Contains(t)) list.Add(t);34
}35
if (list.Count < 1) return true;36
list.Sort(IntSort);37
38
CharObject A = ts[list[0]];39
Byte[] Bts = A.Bts;40
Byte[] Bts2 = A.Bts2;41
42
//處理start以下的字節43
//上層遞歸最多到達start處，而本層就要用到start-1了，44
//處理一下，以免別的子遞歸曾經修改過start-145
if (start > 0) Bts[start - 1] = 0;46
47
//備份A控制的兩個字節，而不一定是Bts[start]和Bts[start－1]48
Byte[] temp_a = new Byte[2];49
temp_a[0] = Bts[A.K];50
temp_a[1] = Bts[A.M];51
foreach (Int32 a in A.NList)52
{53
Bts[A.K] = temp_a[0];54
Bts[A.M] = temp_a[1];55
A.N = a;56
A.Cal();57
if (list.Count < 2)58
{59
if (Bts[start] != Bts2[start]) continue;60
locks.Add(A.ID);61
if (Find(ts, locks, lists, start - 1)) return true;62
locks.Remove(A.ID);63
continue;64
}65
CharObject B = ts[list[1]];66
Byte[] temp_b = new Byte[2];67
temp_b[0] = Bts[B.K];68
temp_b[1] = Bts[B.M];69
foreach (Int32 b in B.NList)70
{71
Bts[B.K] = temp_b[0];72
Bts[B.M] = temp_b[1];73
B.N = b;74
B.Cal();75
if (list.Count < 3)76
{77
//有限個數控制，馬上判斷78
if (Bts[start] != Bts2[start]) continue;79
locks.Add(A.ID);80
locks.Add(B.ID);81
if (Find(ts, locks, lists, start - 1)) return true;82
locks.Remove(A.ID);83
locks.Remove(B.ID);84
continue;85
}86
CharObject C = ts[list[2]];87
Byte[] temp_c = new Byte[2];88
temp_c[0] = Bts[C.K];89
temp_c[1] = Bts[C.M];90
foreach (Int32 c in C.NList)91
{92
Bts[C.K] = temp_c[0];93
Bts[C.M] = temp_c[1];94
C.N = c;95
C.Cal();96
//有限個數控制，馬上判斷97
if (Bts[start] != Bts2[start]) continue;98
locks.Add(A.ID);99
locks.Add(B.ID);100
locks.Add(C.ID);101
if (Find(ts, locks, lists, start - 1)) return true;102
locks.Remove(A.ID);103
locks.Remove(B.ID);104
locks.Remove(C.ID);105
}106
Bts[C.K] = temp_c[0];107
Bts[C.M] = temp_c[1];108
}109
Bts[B.K] = temp_b[0];110
Bts[B.M] = temp_b[1];111
}112
Bts[A.K] = temp_a[0];113
Bts[A.M] = temp_a[1];114
return false;115
}116
浙公網安備 33010602011771號