最小生成樹，Kruskal算法。
算法很簡(jiǎn)單，先把邊排序，依次找鏈接不同集合的最小邊，合并集合，當(dāng)只有一個(gè)集合的時(shí)候結(jié)束。問題在于如何實(shí)現(xiàn)集合合并，學(xué)長(zhǎng)們說合并時(shí)用并查集效率較高。我這里用不同的數(shù)字代表不同的集合，每次合并都要遍歷所有集合，改變集合數(shù)字，時(shí)間復(fù)雜度O(n)。
Ege結(jié)構(gòu)體中剛開始把b、d兩個(gè)變量定義成了char，數(shù)據(jù)小的時(shí)候沒問題，當(dāng)數(shù)據(jù)大于127時(shí)就會(huì)爆掉，糾結(jié)了很久。
qsort()函數(shù)用法：void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
base是數(shù)組起始下標(biāo)；
nelem是元素個(gè)數(shù)；
width是單個(gè)元素的大小；
fcmp是比較函數(shù)。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 600000
typedef struct
{
int x;
int y;
int bl;//set the point belong to
}Point;
typedef struct
{
int b;//begin point//最糾結(jié)的就是這里，剛開始把它定義成了char，爆了很久啊。
int d;//end point
int len;
}Ege;
Point p[760];
Ege eg[LEN];
int cmp(const void *a, const void *b)
{
Ege * a0 = (Ege*)a;
Ege * b0 = (Ege*)b;
return a0 -> len - b0 -> len;
}
int k;
void MakeEge(int n)
{
int i, j;
k = 0;
for(i = 0; i < n - 1; i++)
for(j = i + 1; j < n; j++)
{
eg[k].b = i;
eg[k].d = j;
eg[k].len = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
k++;
}
}
int main()
{
int N, M;
int i, j;
int en;
int min, max;
FILE *fp = fopen("outege.txt", "w");
while(scanf("%d", &N) == 1)
{
en = 0;
for(i = 0; i < N; i++)// read point
{
scanf("%d%d", &p[i].x, &p[i].y);
p[i].bl = i;
}
scanf("%d", &M);
for(i = 0; i < M; i++)//read M eges
{
int b, d, b0, d0;
scanf("%d%d", &b0, &d0);
b = b0 - 1;
d = d0 - 1;
if(p[b].bl != p[d].bl)
{
en++;
min = p[b].bl < p[d].bl ? p[b].bl : p[d].bl;
max = p[b].bl > p[d].bl ? p[b].bl : p[d].bl;
for(j = 0; j < N; j++)// connect set
{
if(p[j].bl == max)
{
p[j].bl = min;
}
}
}
}
MakeEge(N);
qsort(eg, N * (N - 1) / 2, sizeof(Ege), cmp);
for(i = 0; en < N - 1 && i < N * (N - 1) / 2; i++)//test each eges
{
int b, d;
b = eg[i].b;
d = eg[i].d;
if(p[b].bl != p[d].bl)
{
en++;
printf("%d %d\n", b + 1, d + 1);//out this ege
min = p[b].bl < p[d].bl ? p[b].bl : p[d].bl;
max = p[b].bl > p[d].bl ? p[b].bl : p[d].bl;
for(j = 0; j < N; j++)//connect set
{
if(p[j].bl == max)
{
p[j].bl = min;
}
}
}
}
}
return 0;
}
posted @
2012-04-19 17:28 小鼠標(biāo) 閱讀(490) |
評(píng)論 (0) |
編輯 收藏C語(yǔ)言中，文件讀寫相關(guān)的函數(shù)有很多個(gè)，但是從讀寫的數(shù)據(jù)形式來(lái)說可以分為兩類：二進(jìn)制和文本。關(guān)于文本讀寫函數(shù)不多說了，只要會(huì)使用格式化的輸入輸出fscanf()、fprintf()就基本可以解決問題。這里主要說一下二進(jìn)制的文件讀寫函數(shù)fread()和fwrite()。
函數(shù)原型分別為：
size_t fwrite(const void* buffer, size_t size, size_t count, FILE* stream);
size_t fread(void* buffer, size_t size, size_t count, FILE* stream);
其中
buffer是存儲(chǔ)數(shù)據(jù)的指針
size是單個(gè)元素的大小（單位是字節(jié)）
count是元素的個(gè)數(shù)
stream是文件指針
函數(shù)的返回值是實(shí)際讀取或?qū)懭朐氐膫€(gè)數(shù)。
需要注意的是打開供二進(jìn)制讀寫的文件時(shí)讀寫方式后面要多加一個(gè)"b"，表示二進(jìn)制讀寫。例如打開供二進(jìn)制寫入的文件可以為fp = fopen("out.txt", "wb");
用二進(jìn)制存儲(chǔ)文件可以在一定程度上起到文件的保密作用。如果別人用文本編輯器打開我們存儲(chǔ)的二進(jìn)制代碼，ta看到的很可能都是些亂碼。這里之所以所很可能是應(yīng)為如果我們存入的本來(lái)就是文本（char類型）的話，別人還是能夠看到里面的內(nèi)容的。這是因?yàn)閏har的存入是以ASCII的形式存的，這些編碼能夠被文本編輯器識(shí)別。但其他的類型就不行了。
我們來(lái)舉一個(gè)例子：
比如int a = 64（假設(shè)int占兩個(gè)字節(jié)），64的二進(jìn)制為00000000 01000000，若用文本打開，編輯器會(huì)試將a顯示為兩個(gè)字符，一個(gè)ASCII為0的字符，和一個(gè)ASCII為64的字符。0對(duì)應(yīng)的ASCII為null，沒有顯示；64對(duì)應(yīng)的ASCII為字符@, 這是我們能看到的。
如果我們選擇用文本存儲(chǔ)a，系統(tǒng)不會(huì)把a(bǔ)看成數(shù)字，而會(huì)看成由兩個(gè)字符組成的序列：'6'和'4'。'6'的ASCII為54，二進(jìn)制就是00110110，'4'的ASCII為52，二進(jìn)制為00110100。因此a的文本存儲(chǔ)形式對(duì)應(yīng)的二進(jìn)制就是00110110 00110100（要明白，所有數(shù)據(jù)在計(jì)算機(jī)里其實(shí)都是以二進(jìn)制存儲(chǔ)的）。
當(dāng)然，二進(jìn)制存儲(chǔ)文件的根本目的是為了更快速的讀寫數(shù)據(jù)，因?yàn)橛?jì)算機(jī)“喜歡”二進(jìn)制。要想給數(shù)據(jù)加密還必須有加密算法才行。
posted @
2012-04-13 16:59 小鼠標(biāo) 閱讀(1686) |
評(píng)論 (1) |
編輯 收藏
摘要: 題意：求出將上面的數(shù)字變成下面的數(shù)字所需的最少路數(shù)。變換方式只有“加”，“減”，“交換”三種。一道很普通的廣搜題。用used[]記錄各節(jié)點(diǎn)的層數(shù)，以及判斷該結(jié)點(diǎn)是否被訪問過（used[i] == 0 表示沒有訪問過。特別注意初始節(jié)點(diǎn)的層數(shù)為0，但它被訪問過，因此要特殊處理一下。）
Code highlighting prod...
閱讀全文
posted @
2012-03-29 00:02 小鼠標(biāo) 閱讀(190) |
評(píng)論 (0) |
編輯 收藏
深度加回溯，類似于八皇后問題。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char mp[6][6];//map
int len;//map length
int mb;//bigesst
int mbt;//now road length
int CP(int x, int y)//canput
{
int i;
i = y - 1;
while(i >= 0 && mp[x][i] != 'X')
{
if(mp[x][i] == 'O')
return 0;
i--;
}
i = y + 1;
while(i < len && mp[x][i] != 'X')
{
if(mp[x][i] == 'O')
return 0;
i++;
}
i = x - 1;
while(i >= 0 && mp[i][y] != 'X')
{
if(mp[i][y] == 'O')
return 0;
i--;
}
i = x + 1;
while(i < len && mp[i][y] != 'X')
{
if(mp[i][y] == 'O')
return 0;
i++;
}
return 1;
}
void DFS(int n)
{
int i, j;
int x, y;
if(n == len * len)
{
if(mb < mbt)
mb = mbt;
return ;
}
x = n / len;
y = n % len;
if(mp[x][y] == '.' && CP(x, y))
{
mp[x][y] = 'O';
mbt++;
DFS(n + 1);
mbt--;
mp[x][y] = '.';
DFS(n + 1);
}
else
DFS(n + 1);
}
int main()
{
int i, j;
scanf("%d", &len);
getchar();
while(len != 0)
{
for(i = 0; i < len; i++)//read map
gets(mp[i]);
mbt = mb = 0;
DFS(0);
printf("%d\n", mb);
scanf("%d", &len);
getchar();
}
}
這道題跟之前走迷宮的題略有不同，走迷宮時(shí)起始點(diǎn)確定，當(dāng)前點(diǎn)可走的方向確定。而這道題結(jié)束條件是判斷過的格數(shù)超過總格數(shù)。
即使是合法的點(diǎn)也可以選擇不放炮臺(tái)。
posted @
2012-03-08 23:34 小鼠標(biāo) 閱讀(229) |
評(píng)論 (0) |
編輯 收藏
這是《算法設(shè)計(jì)與分析》教材上的一道題，我們老師布置的第一道題。說的是統(tǒng)計(jì)出一本給定頁(yè)碼書中從0~9各個(gè)數(shù)字出現(xiàn)的次數(shù)，頁(yè)碼最高不差過10e9。
窮舉法是很容易想到的，不過當(dāng)輸入過大時(shí)很耗時(shí)間。因此應(yīng)該總結(jié)規(guī)律。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define LEN 20
int bs[] = {0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
int BS = 1111111111;
void StrtoNum(char *str, int *num)
{
int i, len;
len = strlen(str);
*num = 0;
for(i = 0; i < len; i++)
*num = *num * 10 + str[i] - '0';
}
int Pow(int a, int b)
{
int i, t;
t = a;
for(i = 0; i < b - 1; i++)
t *=a;
return t;
}
int GetMod(int a)
{
return BS % Pow(10, a);
}
int main()
{
int i, j;
int nb;// now bit
char nums[LEN];
int num;
int rs[10];// result
int len;
int mh;//most high
int nt;
while(gets(nums) != NULL)
{
memset(rs, 0, sizeof(rs));
len = strlen(nums);
StrtoNum(nums, &num);
//
//printf("num = %d\n", num);
//
mh = nums[len - 1] - '0';
for(i = 0; i <= mh; i++)//init the lowest bit
rs[i] = 1;
for( i = 1; i < len; i++)
{
nb = len - i -1;
mh = nums[nb] - '0';
StrtoNum(&nums[nb + 1], &nt);
//
//printf("mh = %d nt = %d\n", mh, nt);
//
rs[mh] += nt + 1;//@2, mh mh
for(j = 0; j < mh; j++)//@2 others
{
rs[j] += Pow(10, i);
}
for(j = 0; j < 10; j++)//@1
{
rs[j] += mh * bs[i];
}
}
rs[0] -= GetMod(len);
for(i = 0; i < 10; i++)
printf("%d %d\n", i, rs[i]);
}
//getchar();
}
統(tǒng)計(jì)出只有一位數(shù)的情況是很簡(jiǎn)單的，我們來(lái)當(dāng)在統(tǒng)計(jì)好的一個(gè)數(shù)字前面再加上位數(shù)時(shí)統(tǒng)計(jì)結(jié)果會(huì)怎么增加。我們可以把這個(gè)增加的值看做兩部分，一部分是因高位增加導(dǎo)致地位數(shù)的取值范圍增大而導(dǎo)出的，另一部分是高位本身產(chǎn)生的。兩方面的計(jì)算都有規(guī)律可循。要特別注意0的計(jì)算。
請(qǐng)注意庫(kù)函數(shù)pow（）的返回值為double，轉(zhuǎn)換為int時(shí)會(huì)有精度丟失（調(diào)試中的表現(xiàn)為無(wú)論數(shù)據(jù)多大，結(jié)果總跟標(biāo)準(zhǔn)答案相差1），因此這里特地寫了一個(gè)Pow（）函數(shù)做返回值為int的乘方計(jì)算。
posted @
2012-03-08 19:38 小鼠標(biāo) 閱讀(1129) |
評(píng)論 (0) |
編輯 收藏據(jù)說這道題用的是動(dòng)態(tài)規(guī)劃，首先把"s"看成要找的串，其次"se"，其次'sev',直到"seven"，只需將元串掃描5遍即可得到結(jié)果。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 10005
int main()
{
char s1[LEN];
long long rs[6][LEN];
char s0[7] = "@seven";
char s2[7] = "@SEVEN";
int i, j;
int len;
//printf("%d\n", sizeof(long long));
while(gets(s1) != NULL)
{
memset(rs, 0, sizeof(rs));
for(i = 0; i < LEN; i++)
rs[0][i] = 1;
len = strlen(s1);
for(i = 1; i < 6; i++)
for(j = 0; j < len; j++)
{
if(s1[j] == s0[i] || s1[j] == s2[i])
rs[i][j + 1] = rs[i][j] + rs[i - 1][j];
else
rs[i][j + 1] = rs[i][j];
}
printf("%lld\n", rs[5][len]);
/**//*for(i = 0; i < 6; i++)
{
for(j = 0; j < len + 2; j++)
printf("%ld ", rs[i][j]);
putchar(10);
}*/
}
}
再次印證了我的菜鳥身份，long long 的輸出格式為"%lld"，為此WA了三次。
posted @
2012-03-04 17:48 小鼠標(biāo) 閱讀(100) |
評(píng)論 (0) |
編輯 收藏簡(jiǎn)單的走迷宮，廣搜求最短路徑，要把坐標(biāo)搞清楚。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 14
#define QLEN 100000
typedef struct
{
int x;
int y;
int z;
}Point;
typedef struct
{
int f;
int r;
Point *p;
}Queue;
int d[6][3] =
{
0, 0, 1,
0, 0, -1,
1, 0, 0,
-1, 0, 0,
0, 1, 0,
0, -1, 0
};
char sp[LEN][LEN][LEN];//space map
int rl[LEN][LEN][LEN];//road length
Point bg, ed;
int N;
void BFS()
{
int i, j;
Point t;
int x, y, z;
int find = 0;
Queue q;
q.f = q.r = 0;
q.p = (Point*)malloc(sizeof(Point) * QLEN);
q.p[q.f] = bg;
q.r++;
while(q.f != q.r && !find)
{
t = q.p[q.f];
q.f = (q.f + 1) % QLEN;//DeQueue
for(i = 0; i < 6; i++)
{
x = t.x + d[i][0];
y = t.y + d[i][1];
z = t.z + d[i][2];
if(sp[z][y][x] == 'O')//can walk
{
sp[z][y][x] = 'X';//change mp
rl[z][y][x] = rl[t.z][t.y][t.x] + 1;//change rl
q.p[q.r].x = x;//EnQueue
q.p[q.r].y = y;
q.p[q.r].z = z;
q.r = (q.r + 1) % QLEN;
}
else if(sp[z][y][x] == 'E')
{
rl[z][y][x] = rl[t.z][t.y][t.x] + 1;//change rl
find = 1;
}
}
}
free(q.p);
}
int main()
{
int i, j, k, m;
char s1[LEN];
int gard = 100;
while(scanf("%s%d", s1, &N) == 2 && gard--)
{
getchar();
for(i = 1; i <= N; i++)//read space map
for(j = 1; j <= N; j++)
{
for(k = 1; k <= N; k++)
sp[i][j][k] = getchar();
getchar();
}
scanf("%d%d%d", &bg.x, &bg.y, &bg.z);//read point
scanf("%d%d%d", &ed.x, &ed.y, &ed.z);
getchar();
gets(s1);//read END
//getchar();
bg.x += 1;
bg.y += 1;
bg.z += 1;
ed.x += 1;
ed.y += 1;
ed.z += 1;
sp[bg.z][bg.y][bg.x] = 'B';
sp[ed.z][ed.y][ed.x] = 'E';
for(i = 0; i <= N + 1; i++)//init map
for(j = 0; j <= N + 1; j++)
{
sp[i][j][0] = sp[i][j][N + 1] = sp[N + 1][i][j] = '#';
sp[0][i][j] = sp[i][0][j] = sp[i][N +1][j] = '#';
}
for(i = 0; i < LEN; i++)//init road length
for(j = 0; j < LEN; j++)
for(k = 0; k < LEN; k++)
rl[i][j][k] = 0;
BFS();
if(rl[ed.z][ed.y][ed.x] != 0)
printf("%d %d\n", N, rl[ed.z][ed.y][ed.x]);
else if(bg.x == ed.x && bg.y == ed.y && bg.z == ed.z)
printf("%d 0\n", N);
else
printf("NO ROUTE\n");
}
}
這道題交了很多遍一直WA，很是郁悶。剛開始以為自己的隊(duì)列沒有管理好，換成STL隊(duì)列問題依舊，又懷疑輸出格式的問題，修改后問題依舊。最后終于看到BFS（）中有一個(gè)break（寫在了for循環(huán)里面），這樣是跳不出while的，用標(biāo)志find代替break后果然AC！
想和寫之間的確有很大的差距，多些代碼才是硬道理。
scanf("%s",s1)讀取字符串時(shí)對(duì)前面的空白符有過濾作用，并且字符串中間的空白符將被認(rèn)為字符串的結(jié)束標(biāo)志，空白符不會(huì)被讀入
gets(s1)讀取字符串時(shí)對(duì)前面和中間的空白符都沒有過濾，只有換行符才會(huì)被認(rèn)為是字符串的結(jié)束標(biāo)志，該換行符不被認(rèn)為是字符串的一部分
posted @
2012-03-04 12:54 小鼠標(biāo) 閱讀(233) |
評(píng)論 (0) |
編輯 收藏
摘要: 求最短路徑，最直接的廣度優(yōu)先搜索。
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include<stdio.h>#include<string.h>#include<stdlib.h>#define ...
閱讀全文
posted @
2012-03-01 18:38 小鼠標(biāo) 閱讀(160) |
評(píng)論 (0) |
編輯 收藏
深度優(yōu)先搜索加回溯。之前用四叉樹的記錄遍歷迷宮的所有路徑，結(jié)果內(nèi)存超限制了，請(qǐng)教學(xué)長(zhǎng)之后才知道有種算法設(shè)計(jì)方法叫“回溯”，即在沿一條路深度遍歷后再把走過的路標(biāo)記回來(lái)，這樣就能避免影響其它路徑的遍歷。
另外關(guān)于遞歸要說一點(diǎn)，當(dāng)遞歸中涉及到對(duì)全局變量（比如一個(gè)全局的數(shù)組）的修改時(shí)，之前我一直存在的疑問是：如果遞歸式樹狀調(diào)用結(jié)構(gòu)，那么每一時(shí)刻這個(gè)全局的數(shù)組在被誰(shuí)使用呢？如果每層遞歸都能同時(shí)使用該數(shù)組，那數(shù)據(jù)不就亂了嗎？原來(lái)雖然遞歸的調(diào)用可以是樹狀的，但是每一個(gè)時(shí)刻遞歸都是沿著遞歸樹中的一條路在走，一條路走不通了才會(huì)退一步，換個(gè)子樹接著走。這些都是在了解回溯之后才想通的。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char x;
char y;
}Node;
int fd;//have find given length
int T;
int len;
char mp[8][8];//map
void f(int x, int y)
{
if(!fd)
{
if(mp[x - 1][y] == 'D' && len + 1 == T)fd = 1;
else if(mp[x - 1][y] == '.')//go up
{
len ++;
mp[x - 1][y] = 'X';
f(x - 1, y);
len --;
mp[x - 1][y] = '.';
}
if(mp[x][y + 1] == 'D' && len + 1 == T)fd = 1;
else if(mp[x][y + 1] == '.')//go right
{
len ++;
mp[x][y + 1] = 'X';
f(x, y + 1);
len --;
mp[x][y + 1] = '.';
}
if(mp[x + 1][y] == 'D' && len + 1 == T)fd = 1;
else if(mp[x + 1][y] == '.')//go down
{
len ++;
mp[x + 1][y] = 'X';
f(x + 1, y);
len --;
mp[x + 1][y] = '.';
}
if(mp[x][y - 1] == 'D' && len + 1 == T)fd = 1;
else if(mp[x][y - 1] == '.')//go left
{
len ++;
mp[x][y - 1] = 'X';
f(x, y - 1);
len --;
mp[x][y - 1] = '.';
}
}
}
int main()
{
int N, M;
int i, j;
int find;
Node s;
scanf("%d%d%d", & N, & M, & T);
while(N + M + T != 0)
{
for(i = 1; i <= N; i++)//read map
scanf("%s",&mp[i][1]);
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
if(mp[i][j] == 'X')
for(i = 0; i <= N + 1; i++)//init map
mp[i][0] = mp[i][M + 1] = 'X';
for(i = 1; i <= M; i++)
mp[0][i] = mp[N + 1][i] = 'X';
find = 0;
for(i = 1; i <= N && find == 0; i++)//search start point
for(j = 1; j<= M && find == 0; j++)
if(mp[i][j] == 'S')
{
s.x = i;
s.y = j;
find = 1;
}
fd = 0;
len = 0;
f(s.x, s.y);
if(fd == 1)
puts("YES");
else
puts("NO");
scanf("%d%d%d", & N, & M, & T);
}
}
posted @
2012-02-28 17:14 小鼠標(biāo) 閱讀(239) |
評(píng)論 (0) |
編輯 收藏
問題的關(guān)鍵是題目要求沒有給清楚，沒有給出輸入數(shù)據(jù)的范圍。應(yīng)該先將數(shù)字當(dāng)做字符串處理。
#include<stdio.h>
#include<string.h>
int root2(char *s)
{
int sum2 = 0;
int i, len = strlen(s);
for(i = 0; i < len; i++)
sum2 += s[i] - '0';
return sum2;
}
long root(long n)
{
long sum = 0;
while(n)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int main()
{
long sum;
char s[1000];
gets(s);
while(strcmp(s, "0"))
{
sum = root2(s);
while(sum / 10)
{
sum = root(sum);
}
printf("%d\n", sum);
gets(s);
}
}
posted @
2012-02-22 18:31 小鼠標(biāo) 閱讀(92) |
評(píng)論 (0) |
編輯 收藏