算法04|搜索

搜索基本公式

1
2
3
4
5
6
7
8
9
void bfs (int step)
{
	判断边界
	尝试每一种可能  for(i=1;i<=n;i++)
	{
		继续下一步  dfs(step +1);
	}
	返回
}

一个例子

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
include <stdio.h>
int a[10],book[10],total=0;
void dfs(int step)
{
	int i;
	if (step==n+1) {//如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌
			for(i=1;i<=n;i++)
				printf("%d",a[i]);
				printf("\n");
				return;//返回之前的一步
	}
	for(i=1;i<=n;i++)
	{
		if (book[i]==0) {//表示第i号扑克牌仍然在手上
			a[step]=i;
			book[i]=1;
			dfs(step+1);
			book[i]=0;
		}
	}
	return;
}
int main(){
	scanf("%d",&n);
	dfs(1);
	getchar();getchar();
	return 0;
}

迷宫问题

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
#include <stdio.h>
//迷宫问题
struct note
{
	int x;
	int y;
	int f;
	int s;
};
int main()
{
	struct note que[2501];//地图大小不超过50*50
	int a[51][51]={0},book[51][51]={0};
	int next[4][2] = { { 0, 1},
						{ 1, 0},
						{ 0, -1},
						{-1, 0} };
	int head, tail;
	int i,j,k,m,n,startx,starty,q,p,tx,ty,flag;
	
	scanf("%d %d",&n, &m);
	for(i=1; i<=n; i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	scanf("%d %d %d %d",&startx, &starty,&p,&q);
	//队列初始化
	head=1;
	tail=1;
	//插入迷宫入口坐标
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].f=0;
	que[tail].s=0;
	tail++;
	book[startx][starty]=1;	
	flag=0;
	while (head<tail) {
		for(k=0;k<=3;k++)
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			//判断是否越界
			if (tx<1 || tx>n || ty<1 || ty>m) 
				continue;
				//判断是否是障碍物或已经在路径中
			if(a[tx][ty]==0 && book[tx][ty]==0)
			{
				book[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].f=head;
				que[tail].s=que[head].s+1;
				tail++;
			}
			//到达目标点
			if(tx==p && ty==q)
			{
				flag=1;
				break;
			}
		}
		if (flag==1) 
			break;
			head++;	
		
	}	
	printf("%d",que[tail-1].s);
	getchar();getchar();
	return 0;
}

I miss you so much|时光百宝袋01

《马来西亚》
今天走在路上听着coldplay的歌，突然就笑了起来，因为想到了在路上遇见的一个华人司机，我跟竺和沈上车之后他一直不说话，我们以为他不会说中文，然后看见他挂了个佛教的牌子，就自顾自的好奇的谈论起来。突然好笑的是当我们偷偷说他是啥宗教的时候他突然冒出一句中文吓我们一大跳。我下意识的说了一句妈耶，全车的气氛瞬间变的搞笑起来，感觉还是很好玩的，虽然我不记得他长什么样子了。在大马的时候总是会想多记录一点，时光再久一点，我能遇见更多的人。

沈有一次说很多外国友人喜欢跟我合照是因为我总是笑着的，我确实很开心啊，见到每一个人都是这样，这一刻忘记自己是谁，忘记自己想要做什么，忘记自己的压力，忘记自己的身份，忘记社交软件，只是享受着最初的与人交往的感觉，在那里的时光一直都像一个孩子，好奇的想要去发现任何事情，去接触自己所不敢接触的事情。

有时候会突然很迷茫，很难过，不知道自己应该做些什么，其实是知道但又好像不知道，想去努力的抓住什么，想丢掉一些东西，我果然还是很胆小，没有自己想象中那么勇敢去真正抛下一切。会不管未来怎样只是按照自己的内心来，但是矛盾的是，我知道自己内心的想法，但是确不得不去做一些自己讨厌做的事情，因为我还是这个大环境中的一个份子，我必须对自己的未来负责，必须承担自己的责任。

但是有时候又觉得自己是勇敢的，我也不知道。这个19岁的秋天，我还是非常想念吉打州的雨水和冲刷过的发着光芒的槟城。

简单算法思想01|排序

1.桶排序：把对应的数放入对应的桶，然后输出桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main() {
	int a[11],i,j,t;
	for(i = 0;i<=10;i++)
		a[i] = 0;
	for(i=1;i<=8;i++)
	{
		scanf("%d",&t);
		a[t]++;
	}
	for(i = 0;i<=10;i++)
		for(j=0;j<a[i];j++)
		printf("%d",i);
		return 0;
}

优点：简单
缺点：浪费空间

2.冒泡排序：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换 过来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main() {
	int a[100],i,j,t,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<n-1;i++)
	{
		for(j=1;j<=n-1;j++)
		{
			if (a[j]<a[j+1]) {
				t=a[j];a[j]=a[j+1];a[j+1]=t;
			}
		}
	}
	for(i=1;i<=n;i++)
		printf("%d\t",a[i]);
		
		return 0;
		
}

优点：可以结合字符串输出信息。

3.最常用的排序：快速排序（基于一种二分的思想）

首先选择一个数作为基准数（用来参照的数）

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
#include <stdio.h>
int a[100],n;
void quicksort(int left, int right)
{
	int i,j,t,temp;
	if (left>right) 
		return;
		temp = a[left];//存基准数
		i=left;
		j=right;
		while (i!=j) 
		{
			while (a[j]>=temp && i<j) //从右往左找
				j--;
			while (a[i]<=temp && i<j) 
				i++;
			if (i<j) {
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}	
		}
		//最终将基准数归位
		a[left]=a[i];
		a[i]=temp;
		quicksort(left, i-1);
		quicksort(i+1, right);
}
int main() {
	int i,j,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	quicksort(1,n);
	for(i=1;i<=n;i++)
		printf("%d\t",a[i]);
	return 0;
}

Js|构造函数

构造函数调用

如果函数或者方法调用之前带有关键字new，就构成函数调用。构造函数的语法允许省略实参列表和圆括号。
如下面两行代码等价：

1
2
var o=new Object();
var o=new Object;

构造函数调用创建一个新的空对象，这个对象继承自构造函数的prototype属性。 构造的函数会试图初始化新创建的对象。并将这个对象用作调用上下文因此可以使用this关键字来引用所创建的新对象。构造函数一般不使用return关键字。
例如：

1
2
3
4
5
6
7
8
9
10
11
this.name=name;
this.qq=qq;
this.showName=function ()
{
	alert('my name is :'+this.name);
}
this.showQq=function()
	{
		alert('my qq is :'+this.qq);
	};
}//只需在调用时在对象前加new

可变长的实参列表：实参对象

调用函数时传入的实参个数超过函数定义时的形参个数，没办法直接获得未命名值的引用，而参数对象解决了这个问题。
在函数体内，标识符arguments是指向实参对象的引用。

假设定义了函数f，实参只有一个x。如果调用这个函数时传入两个实参，第一个实参可以通过参数名x来获得，也可以通过arguments[0]来得到，第二个实参只能通过arguments[1]来得到，此外，与真正的数组一样，arguments也包含一个length属性，用以标识其所包含元素的个数。因此，如果调用函数f（）时传入两个参数，arguments.length的值就是2.

arduments并不是真正的数组，是一个实参对象。

闭包：函数对象可以通过作用域链相互关联起来。

js采用词法作用域，也就是说，函数的执行依赖与变量作用域。为了实现这种，js内部状态不仅包含函数的代码逻辑，还必须引用当前的作用域链。一定角度来讲，所有的函数都是闭包：它们都是对象，都关联到作用域链。

1
2
3
4
5
6
7
var scope=“global scope”;
function checkscope(){
var scope=“local scope”;
function f(){return scope;}
return f();
}
checkscope();  //local scope

如果是checkscope()();则返回函数内嵌套的一个函数对象

|