Joyce' Blog
0%

发表于 更新于

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

思路

对于复杂度的要求加大了题目的难度，一般容易想到线性级别的解决方法，如果要降到对数级别，要用到二分查找法。这里的二分其实是针对切割的位置。参考了LeetCode上的解答。

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/very-concise-ologminmn-iterative-solution-with-detailed-explanation

为了简化问题，偶数和奇数个数的有序数组，可以综合成一种情况：数组长度为N时，index of L = (N-1)/2, and R is at N/2。 中位数的下标可以表示为(L + R)/2 = (A[(N-1)/2] + A[N/2])/2。函数中使A1是更长的数组。

设想数组中有更多的位置：

1
2
A1: [# 1 # 2 # 3 # 4 # 5 #]    (N1 = 5, N1_positions = 11)
A2: [# 1 # 1 # 1 # 1 #]     (N2 = 4, N2_positions = 9)

两个数组共有2N1 + 2N2 + 2个位置，每次分割后左右分别有N1 + N2个位置，最终的分割应保证L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2，相当于L1 <= R2&&L2 <= R1。

在两种情况下需要对切割的位置做出调整：

  • L1>R2：说明A1左边大数过多，A1的切割点左移，同时A2切割点右移；

  • L2>R1：说明A2左边大数过多，A2的切割点左移，同时A1切割点右移；

    否则，找到的即为中位数的位置，中位数等于(max(L1, L2) + min(R1, R2)) / 2。

C++代码

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
#include<iostream>
#include<vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
	int m = nums1.size();
	int n = nums2.size();
	if (m < n)
		return findMedianSortedArrays(nums2, nums1);

	int lo = 0, hi = n * 2;
	while (lo <= hi)
	{//移动A2的切割点，A2为长度更短的数组
		int c2 = (lo + hi) / 2;
		int c1 = m + n - c2;

		double L1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
		double L2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
		double R1 = (c1 == m*2) ? INT_MAX : nums1[(c1) / 2];
		double R2 = (c2 == n*2) ? INT_MAX : nums2[(c2) / 2];

		if (L1 > R2) lo = c2 + 1;
		else if (L2 > R1)hi = c2 - 1;
		else
			return (((L1> L2)?L1:L2) + ((R1<R2)?R1:R2)) / 2.0;
	}
	return -1;
}
int main()
{
	vector<int> nums1;
	vector<int> nums2;
	for (int i = 0; i < 6; i++)
	{
		cout << i * 2 << " ";
		nums1.push_back(i * 2);
	}
	cout << endl;
	for (int j = 0; j < 9; j++)
	{
		cout << j * j << " ";
		nums2.push_back(j*j);
	}
	cout << endl;
	double a=findMedianSortedArrays(nums1, nums2);
	cout << a << endl;
	return 0;
}

分析

复杂度：O(log(min(N1, N2)))

若下标超出数组界限，可以假设有两个额外的值 INT_MAX at A[-1] 和 INT_MAX at A[N]，不影响结果并且简化了情况。

发表于 更新于

Logistic Regression

对数几率回归(Logistic Regression/Logit regression)也称逻辑回归，用于解决分类问题。在对率回归(对数几率回归的简称)中, 0≤hθ(x)≤1.

#####假设函数

假设函数为$h_\theta(x)=g(\theta^Tx)$，其中$g(z)=\frac{1}{1+e^{-z}}$，$g(z)$叫做Sigmoid Function或者Logistic Function.对数几率函数是Sigmoid函数的一种, 它将z值转化为一个接近0或1的y值, 并且其输出值在z=0z=0附近变化很陡. Sigmoid函数即形似S的函数, 对率函数是Sigmoid函数最重要的代表.
$$
{h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}}
$$

#####决策边界

“0“与”1“的分界线

代价函数

线性回归中用到的代价函数（凸函数）：
$$
{J(\theta)=\frac{1}{m}\sum_{i=1}^m\frac{1}{2}\left(h_\theta(x^{(i)})-y^{(i)}\right)^2}
$$

$$
Cost\left(h_\theta(x^{(i)}),y^{(i)}\right)=\frac{1}{2}\left(h_\theta(x^{(i)})-y^{(i)}\right)^2
$$

Sigmiod函数会使代价函数变成非凸函数。若想使用梯度下降法收敛到全局最小值，需要另外定义对率回归的代价函数，得到凸函数。

对率回归中代价函数：
$$
{J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^my^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))\right]}
$$

$$
{Cost\left(h_\theta(x),y\right)=-ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))}
$$

y的值只有0,1两种情况

梯度下降法求对率回归的代价函数参数

虽然与线性回归的更新规则看起来相同，但假设函数h(x)发生了变化，所以是两个完全不同的东西。可使用特征缩放使梯度下降得更快。

高级优化算法

计算$J(\theta)$和导数项，使用更高级的算法来最小化代价函数。

#####Conjugate gradient

共轭梯度法BFGS
L-BFGS

######优点：

不需要手动选择学习率$\alpha$，含有智能内循环（线搜索算法）自动尝试并选择好的$\alpha$；

收敛得远远快于梯度下降；

例：

代价函数：

1
2
3
4
5
function [jVal,gradient]=costFunction(theta)
jVal = (theta(1)-5)^2+(theta(2)-5)^2;
gradient = zeros(2,1);
gradient(1)=2*(theta(1)-5);
gradient(2)=2*(theta(2)-5);

在Octave中执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>> options=optimset('GradObj','on','MaxIter','100');
>> initialTheta=zeros(2,1)
initialTheta =

   0
   0

>> [optTheta,functionVal,exitFlag]=fminunc(@costFunction2,initialTheta,options) %无约束最小化函数

optTheta =

   5.0000
   5.0000

functionVal =    1.5777e-30
exitFlag =  1 %exitFlag判断是否已经收敛

“一对多”分类算法（1-n）

变成n个独立的二元分类问题，计算$h_\theta^{(1)}(x)$、$h_\theta^{(2)}(x)$…$h_\theta^{(n)}(x)$，得出最大值，选择n个分类器中可信度最高的

课件链接

发表于 更新于

####题目描述

假设给我们一个任意的图，它可能是也可能不是DAG（有向无圈图），推广拓扑排序算法，以使得给定有向图G的输入，它的输出是以下两者之一：
(a) 一个拓扑排序，于是确定了G为DAG；
或者
(b) G中的一个圈，于是确定了G不是DAG.
注意到输出的解可能不是唯一的，输出任意一个答案即可。

输入

第一行两个数n,m,代表节点数和边数
m行，每行两个数代表一条有向边

测试数据范围：(1<=n<=50,0<=m<2500)

输出

YES
一个拓扑序，数字之间用逗号分隔。

或者

NO
一个圈，数字之间用逗号分隔。

思路

由顶点的入度判断是否有环，若无环，则存在拓扑排序，利用队列，不断加入入度为0的顶点，并调整邻接于该点的顶点的入度，输出拓扑排序；若有环，用深度优先搜索找环，创建数组fath存储父节点，若遇到已标记过的点，则找到了环，利用fath数组输出环。代码中有数组越界的问题，但是我还没有找出来(委屈.jpg)……

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
#include<iostream>
#include<queue>
using namespace std;
bool* label;	int * fath; bool flag = true;
void dfs(int**a, int n,int s)
{
	label[s] = true;	
	for (int i = 1; i <= n; i++)
	{
		if (a[s][i])
		{
			if (!label[i])
			{
				fath[i] = s;
				dfs(a, n, i);
			}
			else if(flag)
			{
				queue<int> q;
				int tmp = s;
				while (tmp != i)
				{
					q.push(tmp);
					tmp = fath[tmp];
				}
				q.push(tmp);
				tmp = q.front();
				while (!q.empty())
				{
					cout<<q.front() << ",";
					q.pop();
				}
				cout << tmp << endl;
				flag = false;
				return;
			}
		}
	}

}
void isDAG(int**a,int n,int m)
{
	int* indg = new int[n + 1];
	label = new bool[n + 1];
	queue<int> q;
	for (int i = 1; i <= n; i++)
		indg[i] = 0;
	for (int i = 1; i <= n; i++)
	{
		label[i] = false;
		for (int j = 1; j <= n; j++)
			indg[j] += a[i][j];//计算入度
		if (a[i][i])
		{//自环
			cout << "NO" << endl;
			cout << i << "," << i << endl;
			return;
		}
	}
	while (q.size()<n)
	{
		int min = n; int index;
		for (int i = 1; i <= n; i++)
			if (indg[i] < min && !label[i])
			{
				min = indg[i];
				index = i;
				label[i] = true;
			}
		if (min > 0)
		{
			cout << "NO" << endl;
			break;
		}
		else
		{
			q.push(index);
			for (int i = 1; i <= n; i++)
				indg[i] -= a[index][i];
		}
	}
	if (q.size() == n)
	{
		cout << "YES" << endl;
		while (q.size() > 1)
		{
			cout << q.front() << ",";
			q.pop();
		}
		cout << q.front() << endl;
		q.pop();
	}
	else
	{//不是拓扑排序
		fath = new int[n + 1];
		for (int i = 1; i <= n; i++)
		{
			label[i] = false;
			fath[i] = 0;
		}
		for (int i = 1; i <= n&&flag; i++)
		{
			if (!label[i])
				dfs(a, n,i);
		}
	}
}
int main()
{
	int n, m;//节点数和边数
	cin >> n >> m;
	int**a = new int*[n + 1];
	for (int i = 1; i < n + 1; i++)
	{
		a[i] = new int[n + 1];
		for (int j = 1; j <= n; j++)
			a[i][j] = 0;
	}
	int x, y;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		a[x][y] = 1;
	}
	isDAG(a,n,m);
	system("pause");
	return 0;
}

发表于

算法导论练习题

有一个机器人，从S出发到E去，只能向右或向下走，X表示该格子不能走。问从S到E共有多少种走法。

S
X X
X X
X E 
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
int main()
{
	int a[8][12] = { 
	{0,0,0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,1,1,1,1,1,1,1,0,},
	{0,1,1,0,1,1,1,1,1,0,1,0},
	{0,1,1,1,1,1,1,1,1,1,1,0},
	{0,1,1,1,0,1,1,0,1,1,1,0},
	{0,1,1,1,1,1,1,1,1,1,1,0},
	{0,1,1,1,1,1,1,1,0,1,1,0},
	{0,0,0,0,0,0,0,0,0,0,0,0} };
	int b[8][12];
	for (int i = 1; i <= 6; i++)
		for (int j = 1; j <= 10; j++)
			b[i][j] = a[i][j];
	for (int i = 2; i <=6; i++)
	{
		for (int j = 2; j <=10; j++)
		{
			if(a[i][j])
				b[i][j] = b[i - 1][j] + b[i][j - 1];

		}
	}
	for (int i = 1; i <= 6; i++)
	{
		for (int j = 1; j <= 10; j++)
			cout << setw(4)<<b[i][j];
		cout << endl;
	}
	system("pause");
	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
71
72
73
74
75
76
77
78
79
80
//Dijkstra寻找最短路径（广度优先思想）
//用邻接矩阵实现图的存储，为简化问题，省去对图的定义
//单源最短路径问题：给定源顶点s，求它到其他任意顶点（目的顶点）的最短路径

#include<iostream>
using namespace std;
int Max = 100;
void djstr(int** a, int v, int e)
{
	int* p = new int[v];
	//p[i]：最短路径中顶点i的前驱顶点,
	//从终点开始，逆向即可获取路径
	int* d = new int[v];
	//当前最短路径长度

	int s = 0;
	bool* label = new bool[v];
	for (int i = 0; i < v; i++)
		label[i] = false;

	for (int i = 0; i < v; i++)
		if (a[0][i] > 0)
		{
			p[i] = 0;
			d[i] = a[0][i];
		}		
		else
		{
			p[i] = -1;
			d[i] = Max;
		}
	label[0] = true;
	while (s < v)
	{
		int index=0, min=d[0];
		for(int i=0;i<v;i++)
			if (!label[i]&&d[i] < min)
			{
				min = d[i];
				index = i;
			}
		++s; label[index] = true;
		for (int i = 0; i < v; i++)
		{
			if (a[index][i] + d[index] < d[i])
			{
				d[i] = a[index][i] + d[index];
				p[i] = index;
			}
		}
	}
	d[0] = 0;
	for (int i = 0; i < v; i++)
		cout << d[i] << " ";
	cout << endl;
	for (int i = 0; i < v; i++)
		cout << p[i]+1 << " ";
}
int main()
{
	
	int v = 5;
	int e = 7;
	int b[5][5] = {
	{ 0,4,2,Max,8 },
	{ Max,0,Max,4,5 },
	{ Max,Max,0,1,Max },
	{ Max,Max,Max,0,3 },
	{ Max,Max,Max,Max,0 } };
	int** a = new int*[v];
	for (int i = 0; i < v; i++)
	{
		a[i] = new int[v];
		for (int j = 0; j < v; j++)
			a[i][j] = b[i][j];
	}
	djstr(a, v, e);
	system("pause");
	return 0;
}

发表于 更新于

计算方法，老师很好，思路清晰，娓娓道来，然而，忘得比学的快，实在无奈…嗯还是完成今天课上说的用完全主元高斯消去法解线性方程组吧。先记一下自己踩过的几个坑：

  • 记录完全主元时，不小心定义成了int类型，导致进行取舍后系数为0，返回无解的提示。应定义为double；
  • 上课没理解老师说的“换回去”是什么意思，结果跑出来才大彻大悟——调整完全主元的位置时，行交换不会影响解的顺序，但是第i.j列进行交换时，xi,xj的值也会被交换。最后在修改代码时增加了数组order，用于记录xi的位置变化；
  • 最麻烦的可能还是三层循环里的i.j.k的初始条件吧，调整了好几次……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
-----完全主元高斯消去法解线性方程组-----
输入：未知数的个数N，N*N的系数矩阵A，N*1的向量Y
输出：N*1的向量X

数据结构：矩阵、线性方程组
*/
#include"LinearEqu.h"
int main()
{
	double a[] = {//方程系数矩阵
		0.2368, 0.2471, 0.2568, 1.2671,
		0.1968, 0.2071, 1.2168, 0.2271,
		0.1581, 1.1675, 0.1768, 0.1871,
		1.1161, 0.1254, 0.1397, 0.1490
	};
	double b[] = { 1.8471, 1.7471, 1.6471, 1.5471 };//方程右端项
	LinearEqu equ(4);//定义一个四元方程组对象
	equ.setLinearEqu(a, b);//设置方程组
	if (!equ.solve())
		cout << "Fail" << endl;
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#pragma once
#include<iostream>
#include<iomanip>
using namespace std;
class Matrix
{
public:
	double* elements;
	Matrix(int size = 2);
	~Matrix();
	void setMatrix(double* values);
	double element(int i, int j) {return elements[i*size + j];}
	void printMatrix(double* p,int s);
	int size;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#pragma once
#include"Matrix.h"
class LinearEqu : public Matrix
{
public:
	LinearEqu(int size = 2);
	~LinearEqu();
	void setLinearEqu(double* a, double* b);
	bool solve();
	void printLinearEqu();
	void printSolution();
	double* sums;
	double* solution;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include"Matrix.h"
Matrix::Matrix(int size):size(size) {
	elements = new double[size*size];
}
Matrix::~Matrix() { delete[] elements; }
void Matrix::setMatrix(double* values)
{
	for (int i = 0; i < size*size; i++)
		elements[i] = values[i];
}
void Matrix::printMatrix(double* p, int s)
{
	cout << "The Matrix is:" << endl;
	for (int i = 0; i <size; i++)
	{
		for (int j = 0; j < s; j++)
			cout <<setw(12)<<p[i*s + j] ;
		cout << endl;
	}
}
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
#include"LinearEqu.h"
void swap(double &a, double &b)
{
	double tmp = a;
	a = b;
	b = tmp;
}
LinearEqu::LinearEqu(int size):Matrix(size) {
	sums = new double[size];
	solution = new double[size];
}
LinearEqu::~LinearEqu() {
	delete[]sums;
	delete[] solution;
}
void LinearEqu::setLinearEqu(double* a, double* b) {
	setMatrix(a);
	for (int i = 0; i < size; i++)
		sums[i] = b[i];
}
bool LinearEqu::solve() {
	printMatrix(elements, size);
	int* order = new int[size];
	for (int i = 0; i < size; i++)
		order[i] = i + 1;
	for (int i = 0; i < size; i++)
	{
		int im =i,jm = i;//最大元所在的行号列号
		double max = elements[i*size + i];
		for (int j = i; j < size; j++)
		{			
			for (int k = j; k < size; k++)
			{
				if (max < elements[j*size + k])
				{
					max = elements[j*size + k];
					jm = k;
					
					im = j;
				}
			}
			
		}
		if (max == 0)
			return false;
		else
		{

			if (im != i)//行交换
			{
				for (int k = i; k < size; k++)
				{
					swap(elements[im*size + k], elements[i*size + k]);
					swap(sums[im], sums[i]);
				}
			}
			if (jm != i)//列交换
			{
				swap(order[jm], order[i]);
				for (int k = 0; k < size; k++)
				{
					swap(elements[k*size + i], elements[k*size + jm]);
				}
			}
		}
		//消去
		double m = elements[i*size + i];
		for (int j = i + 1; j < size; j++)
		{
			double n = elements[j*size + i] / m;
			for (int k = i ; k < size; k++)
			{
				elements[j*size + k] = elements[j*size + k]- elements[i*size + k] * n;
			}
			sums[j] = sums[j] - sums[i] * n;
		}
		//判断剩下的一个元素是否等于0（等于0则矩阵的秩不等于矩阵的行数，则无解）
		//这里没有想好，待补充

		printMatrix(elements, size);
	}
	

	//回代
	for (int i = size - 1; i >= 0; i--)
	{
		double m = elements[i*size + i];
		for (int j = i - 1; j >= 0; j--)
		{
			double n = elements[j*size + i] / m;
			elements[j*size + i] = 0;
			sums[j] = sums[j] - sums[i] * n;
		}
	}
	
	for (int i = 0; i < size; i++)
		cout << "x[" << order[i] << "] = " << (solution[i] = sums[i] / elements[i*size + i]) << endl;
	return true;
}
void LinearEqu::printLinearEqu() {
	printMatrix(elements,size);
	printMatrix(sums, 1);
}
void LinearEqu::printSolution() {
	printMatrix(solution, 1);
}

发表于 更新于

Description

Given a string, find the length of the longest substring without repeating characters.

Input: “abcabcbb”
Output: 3

Input: “bbbbb”
Output: 1

Input: “pwwkew”
Output: 3

####Solution

借鉴了别人的思路，让我觉得很巧妙的一点是，忽略子字符串的具体内容，利用数组记录字符的位置，只比较当前字符的位置是否出现在最左端的右边，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lengthOfLongestSubstring(string s)
{
	int m[256];//字符共有256个，ascii码为i的字符最近位置为m[i]
	for (int i = 0; i < 256; i++)
		m[i] = -1;
	int res = 0;//最大的长度
	int left = 0;//左端点的编号
	for (int rg = 0; rg < s.size(); ++rg)
	{
		if (res == 0 || m[s[rg]] < left)
		{//还未开始移动，或在当前子字符串中无字母s[rg]
			res = res > rg - left + 1 ? res : rg - left + 1;
			m[s[rg]] = rg;
		}
		else
		{//当前子字符串中存在字母s[rg]
			left = m[s[rg]] + 1;
			m[s[rg]] = rg;
		}
	}
	return res;
}

对特殊的字符串进行测试：

1
2
3
4
5
6
7
string a = "abcabcbb";
	string b = "bbbbb";
	string c = "pwwkew";
	string d = "122*hfks2ilnuibin";
	string e = "au";
	cout << lengthOfLongestSubstring(a) << " " << lengthOfLongestSubstring(b) << " " 
		<< lengthOfLongestSubstring(c) <<" "<< lengthOfLongestSubstring(d) << " " << lengthOfLongestSubstring(e) << endl;

输出结果为：3 1 3 10 2

在提交时出现的一种错误情况，即对于字符串“au”输出长度为1，经过检查，是因为最开始在初始化m时，将m的元素全部设为了0，上面的代码中已进行了修正。

发表于

BFS & 二分性测试

二部图定义：

​ 二部图是一个图，其中节点集可以划分为X与Y，每条边一段在X中，另一端在Y中。直观地，一个图是二部图，如果能对节点着红色和蓝色，使得每条边有一个红色端点和一个蓝端点。

定理

如果一个图是二部图，那么它不可能存在奇圈。

BFS与二部图的联系

G中没有边与同一层的两个节点相交。这种情况下G是二部图，其中偶数层的节点可以着红色，奇数层的节点可以着蓝色。G中有一条边与同一层的两个节点相交，则存在一个奇圈，不可能是二部图。

依照这一想法，对BFS算法稍作修改，给出二部图的判别方法如下：

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
#include<iostream>
#include<queue>
using namespace std;
const int N = 8;
void print(int** a)
{
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < N; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
}
void BFS(int** a)
{
	queue<int> s;
	int label[N], layer[N];
	for (int i = 0; i < N; i++)
		label[i] = 0;
	int width;
	s.push(1); label[1] = 1;
	while (!s.empty())
	{
		width = s.size();
		int x = 0;
		for (int i = 0; i < N; i++)
			layer[i]= 0;
		while (width--)
		{
            //同一层的节点存在layer中
			int k = s.front();
			s.pop();
			for (int i = 1; i < N; i++)
				if (!label[i] && a[k][i])
				{
					++label[i];
					s.push(i);
					cout << i << " ";
					layer[x++] = i;
				}	
		}
		cout << endl;
        //检查同一层借点是否相连
		for (int j = 0; layer[j]; j++)
		{
			for (int j1 = j + 1; layer[j1]; j1++)
			{
				if (a[layer[j1]][layer[j]])
					cout << "wrong!" << endl;
                //若存在奇圈，则在有两个节点相交的那一层给出提示
			}		
		}
	}
}
int main()
{
    //初始化数据
	int** a = new int*[N];
	for (int i = 0; i < N; i++)
		a[i] = new int[N];
	for (int i = 1; i < N; i++)
		for (int j = 1; j < N; j++)
			a[i][j] = 0;	
	a[1][2] = a[2][1] = a[1][4] = a[4][1] = a[1][6]=a[4][7]=a[7][4]
		= a[2][5] = a[5][7] = a[4][3] = a[6][1] = a[5][2] = a[7][5] = a[3][4] = 1;
	print(a);
    //二分性测试
	BFS(a);
    
	system("pause");
	return 0;
}

发表于 更新于

###Octave的使用

更改提示符

1
2
octave:11> PS1('>>')
>>

添加分号抑制输出

查看帮助：

1
>> help eye

构造10000个随机数并绘制高斯分布：

1
2
>> w=randn(1,10000);
>> hist(w,50)

圆周率：pi ，常数：e

格式化输出

矩阵

横向量：

1
>> v=[1,2,3]

列向量：

1
>> v=[1;2;3]

2*3，所有元素均为1：

1
ones(2,3)

1*3，所有元素均为0：

1
w=zeros(1,3)

5*5单位矩阵：

1
I=eye(5)

3*3高斯随机数矩阵：

1
rand(3,3)

矩阵数乘：

1
C=2*ones(2,3)

读取A[3,2]:

1
>> A(3,2)

读取矩阵A第2列所有元素：

1
>> A(:,2)

读取矩阵A第1行和第3行所有元素：

1
>> A([1 3],:)

将A第二列替换为[10;11;12]：

1
>> A(:,2)=[10;11;12]

在A的最后加上一列:

1
>> A=[A,[100,101,102]]

将A所有的元素合并成一个列向量:

1
>> A(:)

两个矩阵列合并：

1
>> C=[A B]

两个矩阵行合并

1
>> D=[A;B]

移动数据

所用到的数据: featuresX.dat, priceY.dat

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
>> cd E:\桌面 %Octave中不能输入中文，在左上窗口双击打开
>> load featuresX.dat
>> load('priceY.dat')
>> who %使用who命令显示当前所有变量,使用whos查看变量更详细的信息
>> featuresX %展示数据
featuresX =

   2104      3
   1600      3
   2400      3
   1416      2
   3000      4
 ......
>> size(featuresX)
ans =

   27    2
>> v=featuresX(1:5)
v =

   2104   1600   2400   1416   3000

>> save hello.mat v %二进制方式存储数据
>> save hello.txt v -ascii %存储数据
>>clear %清空所有变量
数据的计算
1
2
3
4
5
6
7
8
%各种矩阵的运算
>> A*B
>> A.*b
>> A.^2
>> 1 ./A
>> log(A)
>> exp(A)
>> -A

A中每个元素加1

1
2
3
>> A+ones(size(A))
%或者：
>> A+1

矩阵转置

1
>> A'

最值，比较大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>> A=[1 3 0.5 100]
A =

     1.00000     3.00000     0.50000   100.00000

>> [val ind]=max(A)
val =  100
ind =  4
>> [val]=min(A)
val =  0.50000
>> A>2
ans =

  0  1  0  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
30
31
32
>> A=[1 3 5;6 8 9]
A =

   1   3   5
   6   8   9

>> find(a>3)
error: 'a' undefined near line 1 column 6
>> find(A>3)
ans =

   2
   4
   5
   6

>> [r c]=find(A>=2)
r =

   2
   1
   2
   1
   2

c =

   1
   2
   2
   3
   3

生成任意行、列、对角线和相等的矩阵：

1
2
3
4
5
6
>> magic(3)
ans =

   8   1   6
   3   5   7
   4   9   2

列向量求和

1
2
3
4
>> sum(A)
ans =

    7   11   14
1
2
>> floor(a)%向下取整
>> ceil(a)%向上取整

最值

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
>> A=[1 2;3 4;5 6]
A =

   1   2
   3   4
   5   6

>> A=[1 2;3 4;5 6],
A =

   1   2
   3   4
   5   6

>> B=[3 1;4 6;2 9]
B =

   3   1
   4   6
   2   9

>> max(A,B)
%构造一个由A,B两个矩阵中对应位置较大的数组成的矩阵
ans =

   3   2
   4   6
   5   9

>> max(A,[],1)%取出矩阵每列最大的元素
ans =

   5   6

>> max(A,[],2)%取出矩阵每列最大的元素
ans =

   2
   4
   6
%获取矩阵中最大元素两种方式
>> max(max(A))
ans =  6
>> max(A(:))
ans =  6
>> flipud(A)%矩阵上下翻转
ans =

   5   6
   3   4
   1   2
>> pinv(A)%矩阵的逆
ans =

  -1.33333  -0.33333   0.66667
   1.08333   0.33333  -0.41667
绘图

（将函数画在同一图中、添加坐标轴说明、图示、存储图像、同一窗口不同位置显示两个图像、坐标轴刻度）

将矩阵可视化

1
>> imagesc(magic(15))
控制语句

循环语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>> for i=1:10,
v(i)=i^2;
end;
>> v
v =

     1     4     9    16    25    36    49    64    81   100

>> i=1;
>> while i<=10,
v(i)=sqrt(v(i));
i=i+1;
end;
>> v
v =

    1    2    3    4    5    6    7    8    9   10

定义函数

1
2
3
>> [y1,y2]=squareAndcube(5)
y1 =  25
y2 =  125