因為要解開一個自己忘記密碼的rar檔~(只記得密碼是用幾個常用的密碼組合)，但是市面上的rar程式的字典檔大多數都已經內建好了，不知道要怎麼寫~於是一怒就自己寫了個程式
整個程式其實不難，原本打算用api解開的，可是後來發現只要有灌win rar即可以用他的unrar來解
指令大概是：
C:/Program Files/WinRAR/UnRar x -y"密碼" [filename] [解壓位置]
於是就很簡單的寫了一個程式來不斷的執行他~並且讀取回傳文字
不過其中最麻煩的是密碼破解，我會用的密碼至少就有10組，常用的也有4、5組，外加其他中間配置的 @ at on in..
等加起來，整個跑完也要一段時間，而可能的密碼組也超過數千組吧…(P(15,x))
想想抓得到的解壓縮程式，大多是一組一組的產生，於是也就想要跟他們一樣，讓密碼一組一組產生，而不是全部產生後再來一個一個試：
想歸想，程式其實沒有那麼好寫：畢竟要把密碼排列組合，排列，組合的演算法都是用遞迴寫是最方便的：
最後寫了這樣子的一個演算法：
public String getNextPassword(){
if (getNextFromPermutation() ==null){
int[] combine=getNextFromCombination();
return getNextFromPermuatation();
}else
return getNextFromPermutation();
}
寫成了原始程式碼後就變成這樣子了：
public String getNextString(){
int[] next; //用來排序的數字陣列
next=getPermutationNext(); //取得排列的數字
if(next==null){//表示permutationNext沒了~
setPermutation(getCombinationNext());
next=getPermutationNext();
}
if(next==null)//表示程式結束了
return null;
StringBuffer sb=new StringBuffer();
for (int i:next){
sb.append(words.get(i));
}
return sb.toString();
}
----------------------------------------------------------------
接著重點是：要如何形成一個排列與組合的非遞迴演算法呢？
排列的演算法：我是使用stack來代替遞迴程式碼：
/////////////////////////////////////////
// permutation //
/////////////////////////////////////////
/**
* 將需要排列的數字陣列入setPermutation，然後就可以用getPermutationNext來取
* 接下來的數字陣列排列。
* @param nums
*/
int[] permNums;
int numLength;//記錄permNums的長度
Stack<permNode> stack=new Stack<permNode>();
private void setPermutation(int[] nums){
if(nums==null){//表示不用設定
System.out.println("傳進來的是null,可能程式已結束了");
return;
}
numLength=nums.length;
permNums=new int[numLength];
System.arraycopy(nums,0,permNums,0,numLength);//將值複製到permNums
permNode pn=new permNode(permNums,0);
stack.push(pn);
}
/**
* 取得下一個stack裡面的值~~
* @return
*/
private int[] getPermutationNext(){
permNode node;
while(!stack.isEmpty()){
node=stack.pop();
if(node.n==numLength){//numLength=node.numbers.length
return node.numbers; //end case...表示找到了~~
}else{//表示要繼續進行排列，並且把資料放到stack內。
for(int i=node.n;i<numLength;i++){
//do swap
int temp=node.numbers[i];
node.numbers[i]=node.numbers[node.n];
node.numbers[node.n]=temp;
//copy array of node.numbers...Create new node
int[] tempNumbers=new int[numLength];
System.arraycopy(node.numbers,0, tempNumbers, 0,numLength);
permNode tempNode=new permNode(tempNumbers,node.n+1);
stack.push(tempNode);//放入個新node;
//do swap 換回來
temp=node.numbers[i];
node.numbers[i]=node.numbers[node.n];
node.numbers[node.n]=temp;
}
}
}
return null;
}
class permNode{
public int[] numbers;
public int n;//表示為第幾個數字，在測試時使用
/**
*
* @param numbers 放入的陣列，
* @param n 用來記錄現在數字的值。
*/
public permNode(int[]numbers,int n){
this.numbers=numbers;
this.n=n;
}
}
///////////////////////////////////////
//end of permutation //
//結束permuatation的程式碼 //
//////////////////////////////////////
-------------------------------------------------------------
而組合的方式比較複雜，原本也是打算使用stack的：但我以前有找到一個組合的非遞迴演算法：將他修改後放了上來
//取得C(combM, combN)的值
//pre表示上一組的答案，ans表示這一次回傳的數字~
private int[] getCombinationNext(){
if (pre == null) {//表示程式初次開始。
System.out.println("System start");
pre = new int[combN];
for (int i = 0; i < pre.length; i++) {
pre[i] = i;
}
int[] ret = new int[combN];
System.arraycopy(pre, 0, ans, 0, combN);
return ans;
}
int ni = combN - 1, maxNi = combM - 1;
while (pre[ni] + 1 > maxNi) {//由右至左，找到有增量空間的位置。
ni--;
maxNi--;
if (ni < 0){//若未找到，表示所有的組合均已經取完，
//則可以將n+1，然後進行下一階段的組合
setCombN(++combN);
System.out.println("進行"+combN+"個字的排列組合");
if(combN>combM)
return null;
else{
pre=null;//重新設定
return getCombinationNext();
}
}
}
pre[ni]++;
while (++ni < combN) {
pre[ni] = pre[ni - 1] + 1;
}
int[] ans = new int[combN];
System.arraycopy(pre, 0, ans, 0, combN);
return ans;
}
---------------------------
憑著這兩個演算法：就可以很輕鬆的解開了這次的程式問題
唯一的缺點就是該Permutation其實在處理stack的時候還是會比較慢~~
希望能夠想到其他的方法來取代掉stack
最好是能夠像combination那樣，有一個只需要幾個變數，即可以從上一組資料變出這一組資料的演算法，那就好了
沒有留言:
張貼留言