話說已經三個月沒碰過算法了，真的很無奈，恐怕學到的一點知識全忘光了。
昨天，蘿莉神給我一道題目：
讓我做下，本來懶得做的，但是他說打表就OK了，于是我就欣然答應了。。。奈何他眼中的打表難易度和我眼中不一樣，再次看到了數學系高材生和我的差距，嘿嘿。
第一次嘗試，失敗。
我說，不就是勾股定理a^2+b^2=c^2嗎？結果他說，你再去補補數學知識。。。。
于是給了我一個鏈接，我一看，不就是百度百科的勾股數嗎，于是就暫時擱淺了。
今晚第二次嘗試，仍然失敗。
依稀記得昨天他給我說了有個什么勾股數公式，在百度百科那個勾股數的最下面介紹了，但是我看了半天，還是有點迷糊。
然后讓他把代碼給我看看，好吧，結合百科介紹的勾股數公式，茅塞頓開。
這里給出勾股數公式：
直角三角形三條邊a, b, c，其中a,b是直角邊。
則 a=2*m*n
b=m^2-n^2
c=m^2+n^2
當然，這是有前提條件的，也就是其局限性：“勾股數的公式還是有局限的。勾股數公式可以得到所有的基本勾股數，但是不可能得到所有的派生勾股數。比如6，8，10；9，12，15…，就不能全部有公式計算出來”
也就是說，3,4,5可以求出來，但是其倍數6,8,10就不行了。
這里要注意幾個問題：
1.構成三角形的條件：
2*m*n+m^2-n^2 > m^2+n^2
既m>n
2.a, b, c互質，即無法得到派生的勾股數。
以下是代碼：
// Tanky Woo
// www.WuTianQi.com
#include <iostream>
#define M 1000000
int arr[M+1];
using namespace std;
int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
void init()
{
for(int i=1; i<=800; ++i)
for(int j=i+1; 2*j*j+2*j*i<=M; ++j)
{
int x, y, z;
x=2*i*j;
y=j*j-i*i;
z=j*j+i*i;
//確保x,y,z互質
if(gcd(gcd(x, y), z) == 1)
{
int t = x+y+z;
int tmp = 1;
while(tmp*t <= M)
{
arr[tmp*t]++;
++tmp;
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
init();
int n, m;
while(scanf("%d%d",&n,&m) != EOF){
int pos = 0;
int Max = 0;
for(int i=n; i<=m; i++){
if(arr[i] > Max){
Max = arr[i];
pos = i;
}
}
printf("%d %d\n",pos, Max);
}
return 0;
}
Tanky Woo原創，轉載請注明： 轉載自Tanky Woo
文章標題: 勾股數公式
本文鏈接地址: http://www.wutianqi.com/?p=1632
posted @
2010-12-03 11:19 Tanky Woo 閱讀(5980) |
評論 (2) |
編輯 收藏（最后更新時間：2010.11.26 11點16分）
這個帖子原本是在C++奮斗 樂園論壇討論的，后來覺得有必要和更多朋友分享下，所以就在這里也貼出來了，希望大家一起補充。
因為我個人學的是C/C++的，所以JAVA等程序語言的書籍我就不討論了。
這里討論的主要是C/C++的經典書籍，另外還有計算機專業要學的一些重要課程領域的書，大家一起來補充吧！
我相信經過大家的補充，這篇帖子一定可以幫助許多學C/C++和計科專業學生。
格式是：書名+豆瓣鏈接(最好給出分類)
因為我很多書我也沒看過，所以希望大家能給出書的分類，若我對書的分類有誤，請大家提出，謝謝。
（希望大家把下面的推薦多點下，別讓這個文章沉下去了。謝謝）
C/C++：
《C程序設計語言》http://book.douban.com/subject/1139336/
《C Primer Plus》http://book.douban.com/subject/1319751/
《C陷阱與缺陷》http://book.douban.com/subject/2778632/
《C與指針》http://book.douban.com/subject/3012360/
《C專家編程》http://book.douban.com/subject/2377310/
《編程珠璣》 http://book.douban.com/subject/1910326/
《C++ Primer》http://book.douban.com/subject/1767741/
《C++ Primer Plus》http://book.douban.com/subject/1319751/
《C++程序設計語言》http://book.douban.com/subject/1099889/
《Effective C++》http://book.douban.com/subject/1842426/
《More Effective C++》http://book.douban.com/subject/1453373/
《深度探索C++對象模型》http://book.douban.com/subject/1091086/
《STL源碼剖析》http://book.douban.com/subject/1110934/
《C++標準程序庫》http://book.douban.com/subject/1110941/
數據結構與算法：
《數據結構(C語言版)》嚴蔚敏 http://book.douban.com/subject/2024655/
《數據結構與算法分析》 http://book.douban.com/subject/1971825/
《算法導論》：http://book.douban.com/subject/1885170/
《計算機算法的設計與分析》http://book.douban.com/subject/1683278
Windows 編程
《Windows程序設計》http://book.douban.com/subject/1088168/
《Windows核心編程》http://book.douban.com/subject/1088045/
《深入淺出MFC》http://book.douban.com/subject/1482240/
《VC++深入詳解》http://book.douban.com/subject/1835449/
操作系統：
《計算機的心智:操作系統之哲學原理》http://book.douban.com/subject/3670621/
《現代操作系統 （第2版）》http://book.douban.com/subject/1390650/
《自已動手寫操作系統》http://book.douban.com/subject/1422377/
《深入解析Windows操作系統》http://book.douban.com/subject/2031396/
《深入理解計算機系統》 http://book.douban.com/subject/1230413/
《操作系統設計與實現(第三版)》 http://book.douban.com/subject/2044818/
數據庫：
數據庫系統概論(第四版) http://book.douban.com/subject/1945005/
計算機網絡：
計算機網絡 作者: （美）特南鮑姆 http://book.douban.com/subject/1179807/
《TCP/IP詳解》共三卷
http://book.douban.com/subject/1088054/
http://book.douban.com/subject/1087767/
http://book.douban.com/subject/1058634/
軟件工程：
《人月神話》 http://book.douban.com/subject/2230248/
《重構:改善既有代碼的設計》http://book.douban.com/subject/2989411/
《敏捷軟件開發：原則、模式與實踐》 http://book.douban.com/subject/2347793/
《企業應用架構模式》 http://book.douban.com/subject/4826290/
其他：
《設計模式：可復用面向對象軟件的基礎》http://book.douban.com/subject/1099305/
posted @
2010-11-25 18:57 Tanky Woo 閱讀(4075) |
評論 (13) |
編輯 收藏
摘要: 這是在《C++ Primer》上第十章最后的一個小節。以前把這里漏掉了，剛才看了下，覺得這個程序很不錯，便于對vector, map, set的基本掌握。特地把這一個小程序記錄下來。
/* *目的：一個簡單的文本查詢程序 *作用：程序將讀取用戶指定的任意文本文件，然后允許用戶從該文件中查找單詞。 *查詢的結果是該單詞出現的次數，并列出每次出現所在的行。 *...
閱讀全文
posted @
2010-11-11 20:16 Tanky Woo 閱讀(2699) |
評論 (4) |
編輯 收藏霍納法則(Horner Rule)，是一個比較常用的法則，但是網上關于這個的相關資料不是很多，我主要找到了兩個。
1.http://blog.csdn.net/lwj1396/archive/2008/07/18/2669993.aspx
2.http://flynoi.blog.hexun.com/31272178_d.html
在第二篇文章里講到了霍納法則出現的原因：為多項式求值提供了一個高效的方法。
“對于多項式求值問題，我們最容易想到的算法是求出每一項的值然后把所求的值累加起來，這種算法的時間和空間效率都不高，對于數據規模不大的題目來說由于其直觀、簡單很容易被大家采納，可一旦數據規模過大時，這種算法就顯得無能為力了”
這個算是比較詳細的霍納法則概念了：
假設有n＋2個實數a0，a1，…，an,和x的序列，要對多項式Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０求值，直接方法是對每一項分別求值，并把每一項求的值累加起來，這種方法十分低效，它需要進行n＋(n－1)＋…＋1＝n(n＋１)/2次乘法運算和n次加法運算。有沒有更高效的算法呢?答案是肯定的。通過如下變換我們可以得到一種快得多的算法，即Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０＝((…(((anx ＋an－１)x＋an－２)x+ an－3)…)x＋a1)x＋a０，這種求值的安排我們稱為霍納法則。
在這里我寫了一個霍納法則的小程序：
// Author: Tanky Woo
// blog: www.WuTianQi.com
#include <iostream>
using namespace std;
// Calculate the value of an*x^n + an-1*x^(n-1) + 
a2*x^2 + a1*x + a0
double HornerRule(double a[], int n, double x);
int main()
{
double *a;
int n;
double x;
cout << "Input the n (a0, a1, a2an): ";
cin >> n;
a = new double[n+1];
cout << "Input the a0, a1, a2, , an (n+1 numbers): ";
for(int i=0; i<=n; ++i)
cin >> a[i];
cout << "Input the x: ";
cin >> x;
for(int i=n; i>=0; --i)
{
if(i != n)
cout << " + ";
cout << a[i] << "*x^" << i;
}
cout << " = " << HornerRule(a, n, x) << endl;
return 0;
}
double HornerRule(double a[], int n, double x)
{
double res = 0.0;
for(int i=n; i>=0; --i)
res = x*res + a[i];
return res;
}
posted @
2010-11-11 16:10 Tanky Woo 閱讀(6939) |
評論 (5) |
編輯 收藏軟件課講了這些問題，這次順便總結下。
說白了也就是：遞歸，回溯，深搜或者廣搜。
1.漢諾塔
////////////////////////////////////////////////
/*
漢諾塔
題目：
假設有A, B, C 3個軸，有n個直徑各不相同，
從小到大依次編號為1，2，3，…，n的圓盤
按照從小到大的順序疊放在A軸上。現在要求
將這n個圓盤移至C軸上并仍然按照同樣順序
疊放，但圓盤移動時必須遵守下列規則：
1.每次只能移動一個圓盤，它必須位于某個
軸的頂部。
2.圓盤可以插在A,B,C中任一軸上。
3.任何時刻都不能將一個較大的圓盤壓在較小
的圓盤之上。
*/
///////////////////////////////////////////////
經典的問題，屬于遞歸的入門級問題，但是同樣不好分析，在n<=4以內還可以模擬下漢諾塔的實現，當n>=5時就不太現實了，讓我們來看看漢諾塔當圓盤個數n時有多少組解？ 按照傳說來看：n=64,當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。
但是這畢竟是神話，不過當把64個金片全部放到另外一根針時，確實要很長很長一段時間。
讓我們來看看需要多長時間。
首先，我們找出遞推關系：
f(n + 1) = 2*f(n) + 1
至于這個怎么得到的可以畫圖看看。
把遞推關系算出來后，也就是:
f(n) = 2^n-1
那么當n=64時，是多少？
f(64)= 2^64-1=18446744073709551615
假如每秒鐘一次，共需多長時間呢？一年大約有 31536926 秒，計算表明移完這些金片需要5800多億年，比地球壽命還要長，事實上，世界、梵塔、廟宇和眾生都已經灰飛煙滅。
好吧，說了那么多，還是步入正題。
漢諾塔的實現有遞歸和非遞歸兩種情況，遞歸的很常見，也很簡單，非遞歸實際上就是二叉樹的中序遍歷。也可以認為是棧的實現。
遞歸的版本：
/*遞歸實現*/
#include <iostream>
using namespace std;
//把n號圓盤從x移到y，并打印出。
void Move(int n, char x, char y)
{
cout<< "把" << n << "號圓盤從" << x << "移動到" << y << endl;
}
//把前n個通過b從a移到c
void Hanoi(int n, char a, char b, char c)
{
if(n == 1)
Move(1, a, c);
else
{
Hanoi(n-1, a, c, b);
Move(n, a, c);
Hanoi(n-1, b, a, c);
}
}
int main()
{
int n;
cout << "輸入n的大小: ";
cin >> n;
Hanoi(n, 'a', 'b', 'c');
cout << "Ok!" << endl << "By Tanky Woo." << endl;
return 0;
}
非遞歸的版本有時間再補上。
2.n皇后
對于每一個ACMer,八皇后問題都是必經之路。
作為搜索類題目還是老問題：
1.邊界條件。
2.對每種情況都得遍歷到，可以用解答樹分析。
3.剪枝 http://www.wutianqi.com/?p=1341(搜索與剪枝)
4.輔助空間的變化。回溯前和回溯后的變化。
如果不用輔助空間的回溯當然就不需要注意輔助空間的問題了。
以下是n皇后的源碼：
/*
* n皇后問題
* Tanky Woo
*/
#include <iostream>
using namespace std;
int queen[100];
int n; // n皇后
int tot = 0; //解法種數
// www.wutianqi.com
void search(int cur)
{
if(cur == n) //遞歸邊界。符合要求，輸出。
{
tot++;
for(int i=0; i<n; ++i)
cout << queen[i] << " ";
cout << endl;
}
else
{
for(int i=0; i<n; ++i)
{
bool flag = 1;
queen[cur] = i; // 嘗試把第cur行的皇后放在第i列
for(int j=0; j<cur; ++j) // 檢查是否和前面的皇后沖突
if(queen[cur] == queen[j] // 同一列
|| cur-queen[cur] == j-queen[j] // 正對角線
|| cur+queen[cur] == j+queen[j]) // 反對角線
{
flag = 0;
break;
}
if(flag)
search(cur+1); // 如果合法，繼續
}
}
}
int main()
{
cout << "輸入皇后個數n: ";
cin >> n;
search(0);
cout << "共有" << tot << "種解." << endl << "By Tanky Woo." << endl;
return 0;
}
對于這個問題，還可以用輔助空間來提高算法的效率: 增加輔助空間vis[][]來判斷是否有其他皇后已經在列和對角線上。
#include <iostream>
using namespace std;
int queen[100];
int n; // n皇后
int tot = 0; //解法種數
int vis[3][100]; // 輔助空間
void search(int cur)
{
if(cur == n) //遞歸邊界。符合要求，輸出。
{
tot++;
for(int i=0; i<n; ++i)
cout << queen[i] << " ";
cout << endl;
}
else
{
for(int i=0; i<n; ++i)
{
if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n])
{
queen[cur] = i;
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
search(cur+1);
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; //記住要變化來
}
}
}
}
int main()
{
memset(vis, 0, sizeof(vis));
cout << "輸入皇后個數n: ";
cin >> n;
search(0);
cout << "共有" << tot << "種解." << endl << "By Tanky Woo." << endl;
return 0;
}
3.跳馬問題：
據說此題證明可以用組合數學中的哈密頓環。
組合數學確實博大精深，看過一段時間的組合數學，感覺和實際聯系的很多，Orz.
此題有兩種版本：
①：給定一個N*N的棋盤，起始點在(0,0)處，要求求出有多少種方法，可以不重復的遍歷棋盤上所有的點。
規則：1.馬走日字
2.走過的點就不能再走了
此題和上面的n皇后類似，是標準的DFS。
分析：從起始點開始，每次遍歷八種方向，直到邊界條件，并輸出。
以下是跳馬問題一的源碼：
/*馬跳棋盤問題*/
#include <iostream>
using namespace std;
const int N = 10;
int a[N][N] = {0};
int cnt = 0;
void Horse(int a, int b, int t);
// www.wutianqi.com
int main()
{
int i = 0, j = 0, t = 1;
a[i][j] = t;
Horse(i, j, step+1);
cout << cnt << endl;
cout << "By Tanky Woo.\n";
return 0;
}
void Horse(int a, int b, int t)
{
int x[4] ={-2, -1, 1, 2}, y[4] = {-2, -1, 1, 2};
if(t == N*N+1)
cnt++;
for(int i=0; i<4; ++i)
for(int j=0; j<4; ++j)
{
if(x[i]==y[j] || x[i]==-y[j])
continue;
if(a+x[i]>=0 && a+x[i]<N && b+y[j]>=0 && b+y[j]<N && board[a+x[i]][b+y[j]]==0)
{
a[a+x[i]][b+y[j]] = t;
Horse(a+x[i], b+y[j], t+1);
a[a+x[i]][b+y[j]] = 0;
}
}
}
第二個版本： ②：設有右圖所示的一個棋盤，在棋盤上的A點，有一個中國象棋的馬，并約定馬走的規則：
規則：1. 馬走日字
2. 馬只能向右走。
試找出所有從A到B的途徑。
此題也是OI上很有名的騎士問題。
此題似乎比較適合BFS.
還沒嘗試過。
讓我再想想，好像還有八數碼和素數環問題沒寫。
不過在HDOJ上遇到過一個素數環的題目：
http://www.wutianqi.com/?p=1329
有興趣可以做下。
對于DFS和BFS更多的題目，可以在我博客右上角搜索欄里輸入DFS或BFS，會出來相應題目。
posted @
2010-09-30 15:24 Tanky Woo 閱讀(2552) |
評論 (2) |
編輯 收藏實際上還是稱為區間樹更好理解一些。
樹：是一棵樹，而且是一棵二叉樹。
線段：樹上的每個節點對應于一個線段(還是叫“區間”更容易理解，區間的起點和終點通常為整數)
同一層的節點所代表的區間，相互不會重疊。
葉子節點的區間是單位長度，不能再分了。
線段樹是一棵二叉樹，樹中的每一個結點表示了一個區間[a,b]。a,b通常是整數。每一個葉子節點表示了一個單位區間。對于每一個非葉結點所表示的結點[a,b]，其左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2,b](除法去尾取整）。
線段樹的基本用途：
線段樹適用于和區間統計有關的問題。比如某些數據可以按區間進行劃分，按區間動態進行修改，而且還需要按區間多次進行查詢，那么使用線段樹可以達到較快查詢速度。
線段樹的構建
createSeg //以節點v為根建樹、v對應區間為[l,r]
?{
? 對節點v初始化
if (l!=r)
? {
? 以v的左孩子為根建樹、區間為[l,(l+r)/2]
? 以v的右孩子為根建樹、區間為[(l+r)/2+1,r]
? }
?}
(瀏覽器似乎不太好用了，上面的代碼點“插入代碼”不管用，就直接貼出來了)
個人感覺線段樹比較靈活，要多做一些題目才能對線段樹有一個大概的掌握。
網上看見了一些線段樹的資料，這里也貼出來。
線段樹的一種簡化實現
http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html
線段樹(區間樹)Segment Tree
http://www.wutianqi.com/?p=1140
http://www.wutianqi.com/?p=1369
線段樹基礎知識
http://hi.baidu.com/lemon_cn/blog/item/2093b64bd63797f682025c9f.html
線段樹的構造過程
http://kmplayer.javaeye.com/blog/576486
RMQ問題以及ST算法
http://hi.baidu.com/wjn123335/blog/item/4d485a08414c5ed362d9868a.html
數據結構 – 線段樹
http://www.cnblogs.com/superbin/archive/2010/07/17/1779842.html
http://www.cnblogs.com/superbin/category/253674.html
http://www.cnblogs.com/superbin/archive/2010/08/02/1790467.html
線段樹模版
http://m.shnenglu.com/NicYun/archive/2008/08/05/58037.html
線段樹
http://blog.chinaunix.net/u3/102500/showart_2257428.html
下一篇我會貼出樹狀數組的講解。
posted @
2010-09-25 14:08 Tanky Woo 閱讀(4465) |
評論 (0) |
編輯 收藏
我的獨立博客：http://www.wutianqi.com/
希望大家支持。
謝謝
posted @
2010-09-24 09:22 Tanky Woo 閱讀(248) |
評論 (2) |
編輯 收藏
又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來節約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
字典樹與字典很相似,當你要查一個單詞是不是在字典樹中,首先看單詞的第一個字母是不是在字典的第一層,如果不在,說明字典樹里沒有該單詞,如果在就在該字母的孩子節點里找是不是有單詞的第二個字母,沒有說明沒有該單詞,有的話用同樣的方法繼續查找.字典樹不僅可以用來儲存字母,也可以儲存數字等其它數據。
Trie的數據結構定義：
#define MAX 26
typedef struct Trie
{
Trie *next[MAX];
int v; //根據需要變化
};
Trie *root;
next是表示每層有多少種類的數，如果只是小寫字母，則26即可，若改為大小寫字母，則是52，若再加上數字，則是62了，這里根據題意來確定。
v可以表示一個字典樹到此有多少相同前綴的數目，這里根據需要應當學會自由變化。
Trie的查找（最主要的操作）：
(1) 每次從根結點開始一次搜索；
(2) 取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索； (3) 在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。
(4) 迭代過程……
(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。
這里給出生成字典樹和查找的模版：
生成字典樹：
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = root, *q;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
if(p->next[id] == NULL)
{
q = (Trie *)malloc(sizeof(Trie));
q->v = 1; //初始v==1
for(int j=0; j<MAX; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1; //若為結尾，則將v改成-1表示
}
接下來是查找的過程了：
int findTrie(char *str)
{
int len = strlen(str);
Trie *p = root;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
p = p->next[id];
if(p == NULL) //若為空集，表示不存以此為前綴的串
return 0;
if(p->v == -1) //字符集中已有串是此串的前綴
return -1;
}
return -1; //此串是字符集中某串的前綴
}
對于上述動態字典樹，有時會超內存，比如
HDOJ 1671 Phone List，這是就要記得
釋放空間了：
int dealTrie(Trie* T)
{
int i;
if(T==NULL)
return 0;
for(i=0;i<MAX;i++)
{
if(T->next[i]!=NULL)
deal(T->next[i]);
}
free(T);
return 0;
}
題目分析+解答報告：
HDOJ 1251 統計難題：
http://www.wutianqi.com/?p=1364
HDOJ 1671 Phone List
http://www.wutianqi.com/?p=1366
這里還有幾個字典樹的相關資料，我上傳了RaySource里了，順便和大家分享下：
算法合集之《淺析字母樹在信息學競賽中的應用》
字典樹
posted @
2010-09-24 09:17 Tanky Woo 閱讀(2239) |
評論 (1) |
編輯 收藏半年前在POJ上遇到過一次剪枝的題目，那時覺得剪枝好神秘。。。今天在網上查了半天資料，終于還是摸索到了一點知識，但是相關資料并不多，在我看來，剪枝是技巧，而不是方法，也就是說，可能一點實用的小技巧，讓程序可以少判斷一點，這就是剪枝，剪枝無處不在，
搜索的進程可以看作是從樹根出發，遍歷一棵倒置的樹—-搜索樹的過程。而所謂的剪枝，顧名思義，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是減去了搜索樹中的某些“枝條”，故稱剪枝。
(杭電課件上是這么說的：即剪去解答樹上已被證明不可能存在可行解或最優解的子樹.)
既然采用了搜索，剪枝就顯得十分的必要，即使就簡簡單單的設一個檻值，或多加一兩條判斷，就可對搜索的效率產生驚人的影響。例如Ｎ后問題，假如放完皇后再判斷，則僅僅只算到7，就開始有停頓，到了8就已經超過了20秒，而如果邊放邊判斷，就算到了10，也沒有停頓的感覺。所以，用搜索一般都就要剪枝。
剪枝至少有兩方面，一是從方法上剪枝，如采用分枝定界，啟發式搜索等，適用范圍比較廣；二是使用一些小技巧，這類方法適用性雖不如第一類，有時甚至只能適用一道題，但也十分有效，并且幾乎每道題都存在一些這樣那樣的剪枝技巧，只是每題有所不同而已。
剪枝的原則：
1.正確性：必須保證不丟失正確的結果。
2.準確性：能夠盡可能多的減去不能通向正解的枝條
3.高效性：在很多時候，為了加強優化的效果，我們會增加一些判斷，這樣對程序效率也帶來了副作用，所以要考慮剪枝的高效性，否則得不償失。
最后說一下：剪枝在搜索中用的是非常的廣泛的。
（
參照杭電課件第47頁一句話：
ACMer們：
為了ACM事業，努力地剪枝吧！！
）
題目我不多說，HDOJ 1010就是一個很好的剪枝題目。
HDOJ 1010解答：
http://www.wutianqi.com/?p=1345
另外，杭電的課件–搜索篇里面也講了搜索與剪枝。
posted @
2010-09-19 15:12 Tanky Woo 閱讀(2151) |
評論 (0) |
編輯 收藏原文鏈接：
http://www.wutianqi.com/?p=1284
給定一個帶權的無向連通圖,如何選取一棵生成樹,使樹上所有邊上權的總和為最小,這叫最小生成樹.
求最小生成樹的算法
(1) 克魯斯卡爾算法
圖的存貯結構采用邊集數組,且權值相等的邊在數組中排列次序可以是任意的.該方法對于邊相對比較多的不是很實用,浪費時間.
(2) 普里姆算法
圖的存貯結構采用鄰接矩陣.此方法是按各個頂點連通的步驟進行,需要用一個頂點集合,開始為空集,以后將以連通的頂點陸續加入到集合中,全部頂點加入集合后就得到所需的最小生成樹 .
下面來具體講下：
克魯斯卡爾算法
方法:將圖中邊按其權值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹.(n為頂點數)
第一步:由邊集數組選第一條邊
第二步:選第二條邊,即權值為2的邊
第三步:選第三條邊,即權值為3的邊
第四步:選第四條邊,即權值為4的邊
第五步:選第五條邊
普里姆算法
方法:從指定頂點開始將它加入集合中,然后將集合內的頂點與集合外的頂點所構成的所有邊中選取權值最小的一條邊作為生成樹的邊,并將集合外的那個頂點加入到集合中,表示該頂點已連通.再用集合內的頂點與集合外的頂點構成的邊中找最小的邊,并將相應的頂點加入集合中,如此下去直到全部頂點都加入到集合中,即得最小生成樹.
例在下圖中從1點出發求出此圖的最小生成樹,并按生成樹的邊的順序將頂點與權值填入表中.
———————>先寫出其鄰接矩陣
第一步:從①開始，①進集合，用與集合外所有頂點能構成的邊中找最小權值的一條邊
①——②權6
①——③權1 -> 取①——③邊
①——④權5
第二步:③進集合，①，③與②,④,⑤,⑥構成的最小邊為
①——④權5
③——⑥權4 -> 取③——⑥邊
第三步:⑥進集合，①，③,⑥與②,④,⑤構成的各最小邊
①——②權6
③——②權5
⑥——④權2 -> 取⑥——④邊
第四步:④進集合，①，③,⑥,④與②,⑤構成的各最小邊
①——②權6
③——②權5 -> 取③——②邊
⑥——⑤權6
第四步:②進集合，①，③,⑥,②,④與⑤構成的各最小邊
②——⑤權3 -> 取②——⑤邊
這也是在網上找到的一個Kruskal和Prim構造過程圖，貼出來：
這題的模版我暫時沒找到好的。我覺得這題主要還是思想，當然，給一些題目來練習是必不可少的。
HDOJ 1233 還是暢通工程
HDOJ 1863 暢通工程
HDOJ 1879 繼續暢通工程
http://www.wutianqi.com/?p=1286
HDOJ 1102 Constructing Roads
http://www.wutianqi.com/?p=1313
HDOJ 1875 暢通工程再續
http://www.wutianqi.com/?p=1300
posted @
2010-09-18 01:14 Tanky Woo 閱讀(2491) |
評論 (1) |
編輯 收藏