最小生成树，Kruskal算法。
算法很简单，先把边排序，依次找链接不同集合的最小边，合并集合，当只有一个集合的时候结束。问题在于如何实现集合合并，学长们说合并时用并查集效率较高。我这里用不同的数字代表不同的集合，每次合并都要遍历所有集合，改变集合数字，时间复杂度O(n)。
Ege结构体中刚开始把b、d两个变量定义成了char，数据小的时候没问题，当数据大于127时就会爆掉，纠结了很久。
qsort()函数用法：void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
base是数组起始下标；
nelem是元素个数；
width是单个元素的大小；
fcmp是比较函数。
#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//最纠结的就是这里，刚开始把它定义成了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 小鼠标 阅读(457) |
评论 (0) |
编辑 收藏C语言中，文件读写相关的函数有很多个，但是从读写的数据形式来说可以分为两类：二进制和文本。关于文本读写函数不多说了，只要会使用格式化的输入输出fscanf()、fprintf()就基本可以解决问题。这里主要说一下二进制的文件读写函数fread()和fwrite()。
函数原型分别为：
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是存储数据的指针
size是单个元素的大小（单位是字节）
count是元素的个数
stream是文件指针
函数的返回值是实际读取或写入元素的个数。
需要注意的是打开供二进制读写的文件时读写方式后面要多加一个"b"，表示二进制读写。例如打开供二进制写入的文件可以为fp = fopen("out.txt", "wb");
用二进制存储文件可以在一定程度上起到文件的保密作用。如果别人用文本编辑器打开我们存储的二进制代码，ta看到的很可能都是些乱码。这里之所以所很可能是应为如果我们存入的本来就是文本（char类型）的话，别人还是能够看到里面的内容的。这是因为char的存入是以ASCII的形式存的，这些编码能够被文本编辑器识别。但其他的类型就不行了。
我们来举一个例子：
比如int a = 64（假设int占两个字节），64的二进制为00000000 01000000，若用文本打开，编辑器会试将a显示为两个字符，一个ASCII为0的字符，和一个ASCII为64的字符。0对应的ASCII为null，没有显示；64对应的ASCII为字符@, 这是我们能看到的。
如果我们选择用文本存储a，系统不会把a看成数字，而会看成由两个字符组成的序列：'6'和'4'。'6'的ASCII为54，二进制就是00110110，'4'的ASCII为52，二进制为00110100。因此a的文本存储形式对应的二进制就是00110110 00110100（要明白，所有数据在计算机里其实都是以二进制存储的）。
当然，二进制存储文件的根本目的是为了更快速的读写数据，因为计算机“喜欢”二进制。要想给数据加密还必须有加密算法才行。
posted @
2012-04-13 16:59 小鼠标 阅读(1652) |
评论 (1) |
编辑 收藏
摘要: 题意：求出将上面的数字变成下面的数字所需的最少路数。变换方式只有“加”，“减”，“交换”三种。一道很普通的广搜题。用used[]记录各节点的层数，以及判断该结点是否被访问过（used[i] == 0 表示没有访问过。特别注意初始节点的层数为0，但它被访问过，因此要特殊处理一下。）
Code highlighting prod...
阅读全文
posted @
2012-03-29 00:02 小鼠标 阅读(171) |
评论 (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();
}
}
这道题跟之前走迷宫的题略有不同，走迷宫时起始点确定，当前点可走的方向确定。而这道题结束条件是判断过的格数超过总格数。
即使是合法的点也可以选择不放炮台。
posted @
2012-03-08 23:34 小鼠标 阅读(207) |
评论 (0) |
编辑 收藏
这是《算法设计与分析》教材上的一道题，我们老师布置的第一道题。说的是统计出一本给定页码书中从0~9各个数字出现的次数，页码最高不差过10e9。
穷举法是很容易想到的，不过当输入过大时很耗时间。因此应该总结规律。
#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();
}
统计出只有一位数的情况是很简单的，我们来当在统计好的一个数字前面再加上位数时统计结果会怎么增加。我们可以把这个增加的值看做两部分，一部分是因高位增加导致地位数的取值范围增大而导出的，另一部分是高位本身产生的。两方面的计算都有规律可循。要特别注意0的计算。
请注意库函数pow（）的返回值为double，转换为int时会有精度丢失（调试中的表现为无论数据多大，结果总跟标准答案相差1），因此这里特地写了一个Pow（）函数做返回值为int的乘方计算。
posted @
2012-03-08 19:38 小鼠标 阅读(1054) |
评论 (0) |
编辑 收藏据说这道题用的是动态规划，首先把"s"看成要找的串，其次"se"，其次'sev',直到"seven"，只需将元串扫描5遍即可得到结果。
#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 小鼠标 阅读(90) |
评论 (0) |
编辑 收藏简单的走迷宫，广搜求最短路径，要把坐标搞清楚。
#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，很是郁闷。刚开始以为自己的队列没有管理好，换成STL队列问题依旧，又怀疑输出格式的问题，修改后问题依旧。最后终于看到BFS（）中有一个break（写在了for循环里面），这样是跳不出while的，用标志find代替break后果然AC！
想和写之间的确有很大的差距，多些代码才是硬道理。
scanf("%s",s1)读取字符串时对前面的空白符有过滤作用，并且字符串中间的空白符将被认为字符串的结束标志，空白符不会被读入
gets(s1)读取字符串时对前面和中间的空白符都没有过滤，只有换行符才会被认为是字符串的结束标志，该换行符不被认为是字符串的一部分
posted @
2012-03-04 12:54 小鼠标 阅读(219) |
评论 (0) |
编辑 收藏
摘要: 求最短路径，最直接的广度优先搜索。
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 小鼠标 阅读(145) |
评论 (0) |
编辑 收藏
深度优先搜索加回溯。之前用四叉树的记录遍历迷宫的所有路径，结果内存超限制了，请教学长之后才知道有种算法设计方法叫“回溯”，即在沿一条路深度遍历后再把走过的路标记回来，这样就能避免影响其它路径的遍历。
另外关于递归要说一点，当递归中涉及到对全局变量（比如一个全局的数组）的修改时，之前我一直存在的疑问是：如果递归式树状调用结构，那么每一时刻这个全局的数组在被谁使用呢？如果每层递归都能同时使用该数组，那数据不就乱了吗？原来虽然递归的调用可以是树状的，但是每一个时刻递归都是沿着递归树中的一条路在走，一条路走不通了才会退一步，换个子树接着走。这些都是在了解回溯之后才想通的。
#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 小鼠标 阅读(214) |
评论 (0) |
编辑 收藏
问题的关键是题目要求没有给清楚，没有给出输入数据的范围。应该先将数字当做字符串处理。
#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 小鼠标 阅读(76) |
评论 (0) |
编辑 收藏