21九
归类于程序人生
7 条评论
今天下午没课，正好想起一个比较蛋疼的事情可以做，就是玩c语言的main函数递归。
首先还是说一下我的编译环境，哪些用m$的c语言编译器的朋友可以忽略这个文章了，放心吧，正常情况下是编译不通过的。。。
我的gcc版本是4.2.1。
先贴上代码~
1
2
3
4
5
6
7
8
9
| #include<stdio.h>
#define ____ int
#define _o_ double
#define _O_(x) printf("%c",x)
#define ___(x) 1.0+1199.0*x/12.0-799.0*x*x/24.0+55.0*x*x*x/12.0-5.0*x*x*x*x/24.0
main(____ __)
{
_o_ _;if(!__)main(1);else if(__==6)return;else{_=___(__);_O_((____)(_+0.5));main(__+1);}
} |
跑出来就是一个不换行的Hello
哈哈，这个代码看着很恶心吧。好吧，让我给你翻译一下~如果我把上述代码的define还有一些变量整理一下，那就是这样的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<stdio.h>
int main(int argc)
{
int x;
double ans;
if(argc==0)
main(1);
else{
x=argc;
if(x==6)
return;
else{
ans=1.0+1199.0*x/12.0-799.0*x*x/24.0+55.0*x*x*x/12.0-5.0*x*x*x*x/24.0;
printf("%c",(int)(ans+0.5));
main(x+1);
}
}
} |
现在看明白了么？
关键就是这句
ans=1.0+1199.0*x/12.0-799.0*x*x/24.0+55.0*x*x*x/12.0-5.0*x*x*x*x/24.0;
这个通项正是有穷数列72,101,108,108,111的通项。那么我是如何得到这个表达式的呢？
很简单，用多项式的拉格朗日插值公式就可以解决这个问题。
先把公式贴上来。
至于这个公式是怎么推导出来的，你可以看看这篇论文，讲解的很详细，这里就不复制过来了，哈哈
http://www.lw23.com/pdf_d659df85-fb38-47e6-ac02-147a12d2bab3/lunwen.pdf
有了这个通项就简单了，只要不断递归main函数，理论上可以答应出任意的函数出来。
ps：我求通项的时候用Mathematica来计算的，毕竟当数据多了，展开是个很麻烦的事情。。。然后又先用python写了个函数验证了通项正确后才改写成c的本身递归模式。囧
165 views code, math, program, python, 多项式, 拉格朗日, 数学, 程序, 算法, 编程
31三
归类于程序人生
参与评论
这次的人工智能布置了一个作业，就是用遗传算法求出y=x^2在x属于[1~511]之间的最大值。要用到随机数，二进制转换之类的功能。
所以就随手写了几个，方便需要的朋友拿去使用。
核心算法部分我删掉了。就提供我写的几个小函数，方便大家专注与核心代码的书写。
itoa是用来转换一个整数到二进制的
atoi是把二进制转化成整数的
getrand是用来获取随机初始种群的
getP是用来获取选择概率的
上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
/* Copyright (C) 2010 zerob13 <zerob13@gmail.com> */
#include <iostream>
#include<time.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
using namespace std;
#define MAXNUM 511;//种群范围
#define NUMLEN 8//种群编码长度
#define STNUM 6//种群个体数目
void itoa(int a,int ans[])//输入整数a，和数组ans，然后，a的二进制会存放在ans里。（当然你也可以直接用系统自带的itoa)
{
int i,j;
int co=0;
while(a!=1&&a){
ans[co++]=a%2;
a/=2;
}
if(a)
{
ans[co++]=1;
}
for(i=0,j=NUMLEN-1;i<j;j--,i++)
{
ans[i]^=ans[j];
ans[j]^=ans[i];
ans[i]^=ans[j];
}
}
int atoi(int ans[])//输入二进制数组返回整数值 如数组ans[]={0,0,0,0,0,1,0,1}，就会返回5
{
int an=0,i;
for(i=0;i<NUMLEN;i++)
{
an+=ans[i]*(1<<(7-i));
}
return an;
}
void getrand(int ra[])//获取1~MAXNUM的随机初始种群 放在你输入的数组ra[]中
{
srand(time(NULL));
for(int i=0;i<STNUM;i++)
{
ra[i]=1+rand()%MAXNUM;
}
}
void getP(double P[]){//获取0~1随机数 放在你输入的数组P[]中，作为选择概率用
srand(time(NULL));
for(int i=0;i<STNUM;i++)
{
P[i]=double(rand()%10000)/10000.0;
}
}
void _test_itoa(int ans[])//测试函数
{
itoa(5,ans);
for(int i=0;i<NUMLEN;i++)
{
printf("%d",ans[i]);
}
puts("");
}
void _test_NUM(int ans[])//测试函数
{
_test_itoa(ans);
printf("%d\n",atoi(ans));
}
void _test_rand(int ra[],double P[])//测试函数
{
getrand(ra);
getP(P);
for(int i=0;i<STNUM;i++)
{
printf("%4d",ra[i]);
}
puts("");
for(int i=0;i<STNUM;i++)
{
printf("%lf ",P[i]);
}
puts("");
}
int main (int argc, char * const argv[]) {
int ans[NUMLEN];
int ra[STNUM];
double P[STNUM];
memset(ans,0,sizeof(ans));
_test_NUM(ans);
_test_rand(ra,P);
return 0;
} |
181 views 人工智能, 作业, 小函数, 程序, 算法, 遗传算法
31三
归类于程序人生
2 条评论
题目原型来自HDUOJ的1372 Knight Moves
很简单的一个搜索题
就是告诉你棋盘上的两个点，然后让你算出Knight，也就是国际象棋的马，最少多少步能够从一个点到另一个点。
算法很简单，深搜即可，这个不是本文讨论的问题。这里我是把原来通过函数递归调用的深搜改为用栈自行模拟
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<stdio.h>
#include<stack>
using namespace std;
#define INF 99999
int map[8][8];
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
struct node{
int x,y,t;
};
stack<node>zerob;
int main()
{
char str1[3],str2[3];
node head,p;
while(scanf("%s %s",str1,str2)==2)
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
map[i][j]=INF;
}
}
while(!zerob.empty()){
zerob.pop();
}
head.x=str1[0]-'a';
head.y=str1[1]-'1';
head.t=0;
int ans=-1;
zerob.push(head);
while(!zerob.empty()){
head=zerob.top();
zerob.pop();
if(head.x==str2[0]-'a'&&head.y==str2[1]-'1')
{
if(ans>head.t||ans==-1)
ans=head.t;
continue;
}
for(int i=0;i<8;i++)
{
p=head;
p.x+=dir[i][0];
p.y+=dir[i][1];
if(!(p.x>=0 && p.x<8 && p.y>=0 && p.y<8))
continue;
p.t++;
if(map[p.x][p.y]<=p.t)
continue;
map[p.x][p.y]=p.t;
zerob.push(p);
}
}
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans);
}
} |
后记：
其实当你理解了深搜和广搜后，你会发现，你写出来的深搜和广搜的代码可以看上去是差不多的。为什么那么说呢，因为，无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点——也就是所谓一条路走到死。
同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。
所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。当然，这个只是我个人的理解，欢迎各位大牛拍转。
196 views dfs, 搜索, 数据结构, 栈, 深搜, 算法
24一
归类于程序人生
2 条评论
今天开始学习学习哈夫曼树，于是就去找点题目做做，毕竟学数据结构这种东西还是让oj来验证你的想法最方便了。
google了一下，pku的3252貌似是个软柿子，捏之～
看了一些关于哈夫曼的介绍，大致有个想法了，打出来，wa。。。看来想错了。
于是再看资料，发现需要动态寻找最小的两个节点的，于是就写了一个比较暴力的，参考网上的资料。
6365627 zerob13 3253 Accepted 236K 250MS C++ 628B 2010-01-24 15:08:06
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<stdio.h>
#include<string.h>
#include<stdlib.h>
int lef[20001];
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
int main (int argc, char * const argv[]) {
int i,j,k,l;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
{
scanf("%d",&lef[i]);
}
qsort(lef,n,sizeof(int),cmp);
long long int sum=0;
for(i=1;i<n;i++)
{
lef[i]+=lef[i-1];
sum+=lef[i];
k=lef[i];
for(j=i+1;j<n;j++)
{
if(k>lef[j])
{
lef[j-1]=lef[j];
}else {
break;
}
}
lef[j-1]=k;
}
printf("%lld\n",sum);
}
return 0;
} |
但是很不爽阿，感觉这种代码不是我的风格，于是打算用stl重新写一遍，于是我就开始用stl折腾了。。。
之后就出了一个效率好多了的stl版本。。。
6365653 zerob13 3253 Accepted 348K 32MS C++ 819B 2010-01-24 15:18:24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<stdio.h>
#include<string.h>
#include<queue>
#include<stdlib.h>
using namespace std;
int lef;
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
struct node{
int a;
friend bool operator< (node n1, node n2)
{
return n1.a > n2.a;
}
};
priority_queue<node>zerob;
int main (int argc, char * const argv[]) {
int i,j,k,l;
node kk;
while(scanf("%d",&n)!=EOF){
while(!zerob.empty()){
zerob.pop();
}
for(i=0;i<n;i++)
{
scanf("%d",&lef);
kk.a=lef;
zerob.push(kk);
}
long long int sum=0;
while(zerob.size()>1)
{
node a=zerob.top();
zerob.pop();
node b=zerob.top();
zerob.pop();
sum+=a.a+b.a;
kk.a=a.a+b.a;
zerob.push(kk);
}
printf("%lld\n",sum);
}
return 0;
} |
268 views acm, code, pku3252, 哈夫曼, 数据结构, 树, 算法, 编程
23一
归类于程序人生
参与评论
下学期的数据结构期末作业貌似要做这个，估计就是循环链表的模拟解法吧。。。
所以就凭着记忆写了一个比较简单的cpp版本。
大牛一笑哂之～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<cstdlib>
#include<iostream>
using namespace std;
struct node{
int data;
int index;
node *next,*pre;
}*root,*tail;
void del(node* a)
{
node *p;
p=a->pre;
p->next=a->next;
a->next->pre=p;
cout<<a->index<<endl;
free(a);
return ;
}
void add(int aas,int ind)
{
node *aa=new node;
aa->data=aas;
aa->index=ind;
aa->pre=tail;
tail->next=aa;
aa->next=root;
tail=aa;
root->pre=tail;
}
int main()
{
int i;
int a;
int n,m;
m=4;n=6;
cin>>m>>n;
for(i=0;i<n;i++)
{
cin>>a;
if(i){
add(a,i+1);
}else{
root=new node;
tail=root;
root->data=a;
root->index=i+1;
root->next=tail;
root->pre=tail;
tail->next=root;
tail->pre=root;
}
}
node *tt;
tt=root;
while(n){
int kk=0;
while(1)
{
kk++;
if(kk==m)
{
m=tt->data;
del(tt);
tt=tt->next;
break;
}else {
tt=tt->next;
}
}
n--;
}
} |
123 views cpp, 循环, 数据结构, 算法, 约瑟夫环, 编程, 链表
06十一
归类于程序人生
2 条评论
终于把java的三叉树写出来了～激动！！！热泪～
虽然没有实现自平衡的三叉树，这个是按字母序列存储的，也算是三叉树里面最差的一种吧。。。
上代码～欢迎各位朋友指教～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| package com.zerob13.TernaryTree;
/**
*
* @author yanglingfeng
*/
public class TernaryTree {
private class Node {
char m_char;
Node left, right, middle;
boolean end;
public Node(char ch, boolean e) {
m_char = ch;
end = e;
}
public Node(char ch, boolean e, Node leftc, Node rightc, Node middlec) {
m_char = ch;
end = e;
left = leftc;
right = rightc;
middle = middlec;
}
}
private Node root;
private int count;
/**
* 初始化三叉树
*/
public TernaryTree() {
clear();
}
/**
* 清除三叉树
*/
public final void clear() {
root = null;
count = 0;
}
/**
* 插入一个字符串
* @param s
*/
public void insert(String s) {
root = insert(root, s, 0);
}
/**
* 返回三叉树大小
* @return
*/
public int size() {
return count;
}
/**
* 返回是否能够找到字符串s
* @param s
* @return boolean
*/
public boolean contains(String s) {
return search(root, s, 0) != null;
}
private Node search(Node ref, String s, int pos) {
if (ref == null) {
return null;
} else {
int cmp = s.charAt(pos) - ref.m_char;
if (cmp < 0) {
return search(ref.left, s, pos);
} else if (cmp > 0) {
return search(ref.right, s, pos);
} else {
if (1 + pos == s.length()) {
if (ref.end) {
return ref;
} else {
return null;
}
}
return search(ref.middle, s, pos + 1);
}
}
}
private Node insert(Node ref, String s, int i) {
if (ref == null) {
count++;
ref = new Node(s.charAt(i), false);
}
int cmp = s.charAt(i) - ref.m_char;
if (cmp < 0) {
ref.left = insert(ref.left, s, i);
} else if (cmp > 0) {
ref.right = insert(ref.right, s, i);
} else {
if (i + 1 == s.length()) {
ref.end = true;
} else {
ref.middle = insert(ref.middle, s, i + 1);
}
}
return ref;
}
} |
499 views java, 三叉树, 字符串处理, 搜索, 算法, 高效
15十
归类于程序人生
参与评论
学习Java那么久了，感觉代码量很少。。。所以拿过去用c＋＋写过的一些小东西，还有过去竞赛的一些模板用Java实现来练练手。。。
今天写了一个qsort，没优化的，就是赤裸裸的表现qsort的思想的一个写法。。。
而且感觉C＋＋的味道还很重，没有哪种java的味道。。。哎，路曼曼其修远兮。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| import java.util.*;
/**
*
* @author yanglingfeng
*/
public class Main {
/**
* @param args the command line arguments
*/
static int split(int low, int high,int[] a)
{
int t;
t=a[low];
while(low<high)
{
while(a[high]>t&&low<high)
{
high--;
}
if(low==high)
break;
else
{
a[low]=a[high];
low++;
}
while(a[low]<t&&low<high)
{
low++;
}
if(low==high)
break;
else
{
a[high]=a[low];
high--;
}
}
a[low]=t;
return low;
}
static void qsort(int[] a,int low,int high)
{
int p;
if(low<high)
{
p=split(low,high,a);
qsort(a,low,p-1);
qsort(a,p+1,high);
}
return;
}
public static void main(String[] args) {
// TODO code application logic here
Scanner a=new Scanner(System.in);
int k=a.nextInt();
int[] w=new int[k];
for(int i=0;i<k;i++)
{
w[i]=a.nextInt();
}
qsort(w,0,k-1);
for(int i=0;i<k;i++)
{
System.out.print(w[i]+" ");
}
System.out.println();
}
} |
125 views j2se, java, qsort, 算法
26八
归类于程序人生
参与评论
以前写的婚配模板，测试了多个题目，挺可靠的，于是发出来共享~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| //婚配问题 by 混沌的云Knight
//传入男人数n，女人数m
//男人对女人好感矩阵mtw，女人对男人好感矩阵wtm，匹配矩阵
//match1，match2 匹配成功返回1，否则返回0
//match1,match2返回一个成功婚姻匹配,未匹配顶点match值为-1
#include<string.h>
#define MAXN 502
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
char W[MAXN][MAXN];
int _O[MAXN];
int marry(int n,int m,int mtw[][MAXN],int wtm[][MAXN],int *match1,int *match2)
{
int i=0,j,h,M,t=-1,s1=n,s2=m;
memset(W,0,sizeof(W));
for(_clr(match1),_clr(match2);i<n;_O[++t]=i,i++);
while(t>=0)
{
h=_O[t--];
for(M=-1,i=0;i<m;i++)
if(!W[h][i]&&(M==-1||mtw[h][i]>mtw[h][M]))
M=i;
W[h][M]=1;
if(match2[M]==-1)
{
match1[h]=M;
match2[M]=h;
s1--;s2--;
}else if(wtm[M][h]>wtm[M][match2[M]])
{
match1[match2[M]]=-1;
_O[++t]=match2[M];
match1[h]=M;
match2[M]=h;
}else
_O[++t]=h;
}
return (!s1)||(!s2);
} |
331 views acm, C#, code, cpp, 匹配, 图论, 婚姻匹配, 模板, 稳定婚姻, 算法, 编程
26八
归类于程序人生
4 条评论
今天做了一场topcoder，终于让我的万年灰号变成绿色的了。。。
虽然么有cha人代码，呵呵
今天的题目不是很难，所以比较轻松的解决了前两个水题
第一题ImportantTasks是给你两堆数字，让你找出上一堆比下一堆小的数最多有几对，要一一对应。。。
排序，然后直接水过…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
class ImportantTasks
{
public:
int maximalCost(vector <int> complexity, vector <int> computers)
{
bool hashh[100]={0};
int i,j,k=0,l;
sort(complexity.begin(),complexity.end());
sort(computers.begin(),computers.end());
for(i=complexity.size()-1;i>=0;i--)
{
l=complexity[i];
for(j=0;j<computers.size();j++)
{
if(l<=computers[j]&&!hashh[j])
{
hashh[j]=1;
k++;
break;
}
}
}
return k;
} |
第二题KnightsTour就是骑士走棋盘，不过有些点不能走，而且每个点要动态更新权值。。。暴力+模拟。。。水过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
| #include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
int as[9][9];
int dir[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
class KnightsTour
{
public:
int visitedPositions(vector <string> board)
{
int k,i,j;
struct knight{
int x,y;
int t;
bool ha[9][9];
bool move(vector <string> bo)
{
int i,j,k,si,sj,ax=-1,ay=-1,ass=-1;
for(i=0;i<8;i++)
{
si=x+dir[i][0];
sj=y+dir[i][1];
if(si<0||sj<0||si>=8||sj>=8)
continue;
if(ha[si][sj])
continue;
if(bo[si][sj]=='*')
continue;
if(ax==-1||(ass>as[si][sj])||(ass==as[si][sj]&&ax>si)||(ass==as[si][sj]&&ax==si&&ay>sj))
{
ax=si;
ay=sj;
ass=as[si][sj];
}
}
if(ax!=-1)
{
ha[ax][ay]=1;
x=ax;
y=ay;
t++;
memset(as,0,sizeof(as));
for(i=0;i<bo.size();i++)
{
for(j=0;j<bo[i].length();j++)
{
if(bo[i][j]=='.'&&!ha[i][j])
{
for(k=0;k<8;k++)
{
si=i+dir[k][0];
sj=j+dir[k][1];
if(si<0||sj<0||si>=8||sj>=8)
continue;
if(bo[si][sj]!='*'&&!ha[si][sj])
as[i][j]++;
}
}
}
}
return 1;
}else
return 0;
}
};
knight head;
memset(as,0,sizeof(as));
for(i=0;i<board.size();i++)
{
for(j=0;j<board[i].length();j++)
{
if(board[i][j]=='K')
{
head.x=i;
head.y=j;
head.t=1;
memset(head.ha,0,sizeof(head.ha));
head.ha[head.x][head.y]=1;
break;
}
}
}
for(i=0;i<board.size();i++)
for(j=0;j<board[i].length();j++)
{
if(board[i][j]=='.')
{
for(k=0;k<8;k++)
{
int si=i+dir[k][0];
int sj=j+dir[k][1];
if(si<0||sj<0||si>=8||sj>=8)
continue;
if(board[si][sj]!='*'&&!head.ha[si][sj])
as[i][j]++;
}
}
}
while(head.move(board));
return head.t;
} |
第三题没能看完，因为临时有事情出去了。。。回来一看，自己的号终于变绿了。。。
话说今天这一场是facebook赞助的。。。
176 views code, facebook, topcoder, 升级, 算法, 编程
25八
归类于程序人生
参与评论
所谓的归并排序，就是递归“把数组从中间分开，分成两段，然后分别排序，最后合并”这个过程。
比较好理解，所以很快敲出了代码。
比快排好理解。。。个人感觉。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<stdio.h>
#include<stdlib.h>
typedef int mytype;
void add(mytype *a,int l1,int h1,int l2,int h2)
{
mytype *t;
int i,j,k;
i=l1;
j=l2;
k=0;
t=(mytype*)malloc((h2-l1+1)*sizeof(mytype));
//申请空间存放中间数据
while(i<=h1&&j<=h2)
{
if(a[i]<a[j])
{
t[k++]=a[i++];
}else
{
t[k++]=a[j++];//小的放进去。。。
}
}
while(i<=h1)
{
t[k++]=a[i++];
}
while(j<=h2)
t[k++]=a[j++];//多余的数
for(i=l1,j=0;i<=h2;i++,j++)
{
a[i]=t[j];//复制中间数据回去
}
free(t);
return ;
}
void MergeSort(mytype *a,int low,int high)
{
int mid=(low+high)/2;
if(low<high)
{
MergeSort(a,low,mid);//最难理解的部分了吧。。。
MergeSort(a,mid+1,high);//就是不断的递归
add(a,low,mid,mid+1,high);//然后从最底一层排序后回溯上来。。。
}
return ;
}
int main()
{
mytype s[100];
int i,j,k,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",s+i);
}
MergeSort(s,0,n-1);
for(i=0;i<n;i++)
{
printf("%d ",s[i]);
}
puts("");
}
} |
145 views C#, code, MergeSort, sort, 归并排序, 排序, 算法, 递归
