Posted on | In |
Words count in article: 680 | Reading time ≈ 4

Simple Linear Regression

  • A bunch of data points (xi, yi) are collected
  • Assume x and y are linearly correlated

1

Linear Regression Formulation

1

想要求解得β0和β1使SSE最小，就要做微分

Solving Least-squares Problem

  • SSE is minimized when its gradient with respect to each parameter is equal to zero:

1

Least-squares Solution

  • Suppose there exists N data points:

1

Polynomial Curve Fitting: polyfit()

  • Curve fitting for polynomials of different orders
1
2
3
x = [-1.2 -0.5 0.3 0.9 1.8 2.6 3.0 3.5];
y = [-15.6 -8.5 2.2 4.5 6.6 8.2 8.9 10.0];
fit = polyfit(x,y,1);

1 代表一次方得polynomial， 即f(x) = ax + b
上例中 fit(1) -> a, fit(2) -> b 

1
2
3
4
5
xfit = [x(1):0.1:x(end)];
yfit = fit(1)*xfit + fit(2);
plot(x, y, 'ro', xfit, yfit);
set(gca, 'FontSize', 14);
legend('data points', 'best-fit');

Are x and y Linearly Correlated?

  • if not, the line may not well describe their relationship
  • Check the linearity by using:
  • scatter(): scatterplot 画散点图
  • corrcoef(): correlaition coefficient, -1<= r <= 1 相关系数 很强正相关 趋近1 ，很强负相关 趋近-1
1
2
3
4
x = [-1.2 -0.5 0.3 0.9 1.8 2.6 3.0 3.5];
y = [-15.6 -8.5 2.2 4.5 6.6 8.2 8.9 10.0];
scatter(x, y); box on; axis square;
corrcoef(x, y)

corrcoef(x, y) 得到一个矩阵，对应x跟x、x跟y、y跟x、y跟y的相关系数

Higher Order Polynomials

1
2
3
4
5
6
7
8
9
x = [-1.2 -0.5 0.3 0.9 1.8 2.6 3.0 3.5];
y = [-15.6 -8.5 2.2 4.5 6.6 8.2 8.9 10.0];
figure('Position', [50 50 1500 400]);
for i=1:3
    subplot(1,3,i); p = polyfit(x, y, i);
    xfit = x(1):0.1:x(end); yfit = polyval(p, xfit);
    poly(x, y, 'ro', xfit, yfit); set(gca, 'FontSize', 14);
    ylim([-17, 11]); legend('Location', 'SouthEast','Data points', 'Fitted curve');
end

is it better to use higher order polynomials?

no ,过拟合

What if There Exists More Variables?

  • Equations associated with more than one explanatory variables:

y = β0 + β1x1 + β2x2

  • Multiple linear regression: regress()
  • Note: the function gives you more statistics of the regression model

Multiple Linear Regression: regress()

1

What if the Equations Are Not Linear?

  • How do we do curve fitting using nonlinear equations?

使用cftool工具

Interpolation内插 vs Regression回归

  • Interpolation:
    • The process of finding an approximation of a function
    • The fit does traverse all known points

  • Regression:

    • The process of finding a curve of best fit
    • The fit generally does not pass through the data points

Linear Interpolation: interpl()

1
2
3
4
5
6
7
8
9
10
11
12
13
x = linspace(0, 2*pi, 40); x_m = x;
x_m([11:13, 28:30]) = NaN; y_m = sin(x_m);
plot(x_m, y_m, 'ro', 'MarkerFaceColor', 'r');
xlim([0, 2*pi]); ylim([-1.2, 1.2]); box on;
set(gca, 'FontName', 'symbol', 'FontSize', 16);
set(gca, 'XTick', 0:pi/2:2*pi);
set(gca, 'XTickLabel', {'0','p/2','p','3p/2','2p'});

m_i = ~isnan(x_m);
y_i = interpl(x_m(m_i), y_m(m_i), x);
hold on;
plot(x, y_i, '-b', 'LineWidth', 2);
hold off;

Spline Interpolation: spline()

更圆滑的内插

1
2
3
4
5
m_i = ~isnan(x_m);
y_i = spline(x_m(m_i), y_m(m_i), x);
hold on; plot(x, y_i, '-g', 'LineWidth', 2); hold off;
h = legend('Original', 'Linear', 'Spline');
set(h, 'FontName', 'Times New Roman');

Posted on | In |
Words count in article: 117 | Reading time ≈ 1

Figures are always more powerful

1
2
3
4
5
6
7
8
9
10
11
12
>> x = 1:14;
>> freqy = [1 0 1 0 4 0 1 0 3 1 0 0 1 1];
>> subplot(1,3,1);
>> bar(x, freqy);
>> xlim([0 15]);
>> subplot(1,3,2);
>> area(x, freqy);
>> xlim([0 15]);
>> subplot(1,3,3);
>> stem(x, freqy);
>> xlim([0 15]);
>>

1

Boxplot

1

1
2
3
4
5
6
7
8
9
>> marks = [80 81 81 84 88 92 92 94 96 97];
>> boxplot(marks)
>> prctile(marks,[25 50 75])  % 百分比处的值

ans =

    81    90    94

>>

1

Skewness

1

Kurtosis

1

Posted on | In |
Words count in article: 328 | Reading time ≈ 1

Gaussian Elimination - rref()

高斯消元解方程组

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

A =

     1     2     1
     2     6     1
     1     1     4

>> b = [2; 7; 3]

b =

     2
     7
     3

>> R = rref([A b])

R =

     1     0     0    -3
     0     1     0     2
     0     0     1     1

>>

LU Factorization

LU解法，将A拆解为一个下三角矩阵和一个上三角矩阵乘积

1

下三角矩阵对角线都为1 上半三角都为0

上三角矩阵对角线无所谓，下半三角都为0

1

How to Obtain L and U?

  • the matrices L and U are obtained by using a serious of left-multiplication

1

LU Factorization - lu()

1
2
A = [1 1 1; 2 3 5; 4 6 8];
[L, U, P] = lu(A);

Matrix Left Division: \ or mldivide()

  • Solving systems of linear equations Ax = b using factorization methods:

一定要用左除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>> A = [1 2 1;2 6 1;1 1 4];
b = [2; 7; 3];
x = A\b

x =

   -3.0000
    2.0000
    1.0000

>> x = b/A
错误使用  / 
矩阵维度必须一致。
 
>>

Cramer’s(Inverse) Method

1
2
3
A = [1 2 1; 2 6 1; 1 1 4];
b = [2; 7; 3];
x = inv(A)*b

Singular

  • The inverse matirx does not exist

当矩阵的解有无限多或者无解时候，那么这个矩阵就不存在逆inv(A)

同时,det(A) = 0

Problem with Cramer’s Method

  • the accuracy is low when the determinant is very close to zero(det(A) ~ 0)

Eigenvalues and Eigenvectors

eig()

  • Find the eigenvalues and eigenvectors:
1
[v, d] = eig([2 -12; 1 -5])

Posted on | In |
Words count in article: 468 | Reading time ≈ 2

Symbolic Root Finding Approach

  • Performing mathematics on symbols, NOT numbers
  • The symbols math are performed using “symbolic variables”
  • use sym or syms to create symbolic variables

就是利用sym来创建一个未知数x

1
2
3
syms x
x + x + x  %就是3x
(x + x + x)/4 %就是（3/4）x

或者

1
2
3
x = sym('x');
x + x + x
(x + x + x)/4

同时用未知数去定义一个量，那个量也变为未知数

例如：

1
y = x^2 - 2*x -8

Symbolic Root Finding: solve()

  • Function ‘solve’ finds roots for equations

对于：y = x*sin(x) - x = 0

1
2
syms x
solve('x*sin(x)-x', x)
1
2
3
syms x
y = x*sin(x)-x;
solve(y, x)

Solving Multiple Equations

  • solve this equation using symbolic approach:

{

x - 2y = 5

x + y = 6

}

1
2
3
4
5
6
syms x y
eq1 = x - 2*y - 5;
eq2 = x + y - 6;
A = solve(eq1, eq2, x, y);
A.x
A.y

Solving Equations Expressed in Symbols

  • what if we are given a function expressed in symbols?

a*x^2 - b = 0

1
2
syms x a b
solve('a*x^2-b')
  • x is always the first choice to be solved
  • what if one wants to express b in terms of a and x?
1
2
syms x a b
solve('a*x^2-b','b')

Symbolic Differentiation微分: diff()

  • Calculate the derivative of a symbolic function:

y = 4*x^5

1
2
3
syms x 
y = 4*x^5
yprime = diff(y)

Symbolic Integration积分: int()

1

1
2
3
4
syms x;
y = x^2*exp(x);
z = int(y);
z = z-subs(z, x, 0)

fsolve()

  • A numeric root solver
  • For example, solve this equation:

f(x) = 1.2x + 0.3 + x*sin(x)

1
2
f2 = @(x)  (1.2*x+0.3+x*sin(x));
fsolve(f2, 0)

其中fsolve的第二个参数是对方程成立的x的大概范围猜测，上面例子猜测为0

fzero()

  • Another numeric root solver
  • Find the zero if and only if the function crosses the x-axis
1
2
f = @(x) x.^2;
fzero(f, 0.1) % fzero解不出来 因为x^2 没有穿过x轴 但是fsolve(f, 0)能解出来
1
2
f = @(x) x;
fzero(f, 0.1)  %能解出来

fzero第二个参数也类似fsolve

Finding Roots of Polynomials: roots()

  • find the roots of the polynomial
  • roots only works for polynomial
1
roots([1 -6 -12 81])  % f(x) = x^3-6*x^2-12*x+81

求解root 两种原理：

Bisection 二分法

Newton-Raphson Method(Open) 牛顿法

Assumption:

  • f(x) continusous
  • f`(x) known

1

1

Posted on | In |
Words count in article: 658 | Reading time ≈ 3

Representing Polynomials in MATLAB

  • Polynomials were represented as row vectors
  • For example: f(x) = x^3 - 2*x - 5
  • to enter this polynomial into MATLAB, use p = [1 0 -1 -5];

values of polynomials : polyval()

  • plot the polynomial

f(x) = 9x^3 - 5x^2 + 3x + 7 (for -2 <= x <= 5)

1
2
3
4
5
6
a = [9, -5, 3, 7];
x = -2:0.01:5;
f = polyval(a, x);
plot(x, f, 'LineWidth', 2);
xlabel('x'); ylabel('f(x)');
set(gca, 'FontSize', 14);

Polynomial Differentiation微分: polyder()

1
2
p = [5 0 -2 0 1];
polyder(p)

算某处微分值：

1
2
p = [5 0  -2 0 1];
polyval(polyder(p), 7)

Polynomial Integration积分 ： polyint()

需要多给matlab一个常熟项，积分后会出现一个常数项

1
2
p = [5 0 -2 0 1];
polyint(p, 3)

在某处的值

1
polyval(polyint(p, 3), 7)

Numerical数值 Differentiation微分

Differences: diff()

  • diff() calculates the differences between adjacent相邻 elements of a vector
1
2
x = [1 2 5 2 1];
diff(x)

obtain the slope坡度 of a line between 2 points (1, 5) and (2, 7)

1
2
x = [1 2]; y = [5 7];
slope = diff(y)./diff(x)

Numerical Differentiation Using diff()

  • Given f(x) = sin(x), find f`(x0) at x0 = pi/2 using h = 0.1
1
2
3
4
x0 = pi/2; h = 0.1;
x = [x0 x0+h];
y = [sin(x0) sin(x0+h)];
m = diff(y)./diff(x)

How to Find the f` over an interval [0, 2Π]?

1
2
3
h = 0.05; x = 0:h:2*pi;
y = sin(x); m = diff(y)./diff(x);
plot(m);

Second and Third Derivatives 二次/三次微分

1
2
3
4
5
6
7
8
9
x = -2:0.005:2; y = x.^3;
m = diff(y)./diff(x);
m2 = diff(m)./diff(x(1:end-1));

plot(x, y, x(1:end-1), m, x(1:end-2), m2);
xlabel('x', 'FontSize', 18);
ylabel('y', 'FontSize', 18);
legend('f(x) = x^3', 'f''(x)', 'f''''(x)');
set(gca, 'FontSize', 18);

1

Numerical Integration

用矩形或梯形来估算面积大小来作为积分值

Midpoint矩形估算 Rule Using sum()

底乘高，底是h ， 高是中等分点的函数值

1
2
3
4
h = 0.05; x = 0:h:2;
midpoint = (x(1:end-1)+x(2:end))./2;
y = 4*midpoint.^3;
s = sum(h*y);

Trapezoid Rule 梯形预测

上底加下底乘高除二

上底是x1的函数值 下底是x0的函数值 高是h

1
2
h = 0.05; x = 0:h:2; y = 4*x.^3;
s = h*trapz(y)  % trapz() 就是计算上底加下底除二

或者：

1
2
3
h = 0.05; x = 0:h:2; y = 4*x.^3;
trapezoid = (y(1:end-1)+y(2:end))/2;
s = h*sum(trapezoid)

Second-order Rule: 1/3 Simpson’s

计算面积的公式为：

h/3*(f0 + 4f1 + f2)

1

Review of Function Handles (@)

  • A handle is a pointer to a function
  • can be used to pass functions to other functions
1
2
3
4
5
function [y] = xy_plot(input, x)
% xy_plot receives the handle of a function and plots that function of x
y = input(x); plot(x, y 'r--');
xlabel('x'); ylabel('function(x)');
end

Try: xy_plot(@sin, 0:0.01:2*pi);

不能将函数传给函数，只能传一个函数的handle给另一个函数

Numerical Integration积分: integral()

1
2
y = @(x) 1./(x.^3-2*x-5);
integral(y,0,2)

Double and Triple Integrals

1

Posted on | In , |
Words count in article: 2.4k | Reading time ≈ 15

1.（What a Simple Research）(30 Points)

Doctor Li is doing some research on Chinese ancient
music. Many Chinese ancient music has only five kinds of tones, which can be denoted by
‘C’,‘D’,‘E’,‘G’, and ‘A’. Given a piece of music score, Li wants to do some simple statistics.

Input

There are no more than 20 test cases.

In each test case:

The first line contains two integers n and m (2 <= n, m<=20), indicating that a piece of music
score is represented by an n*m matrix of tones. Only ‘C’,‘D’,‘E’,‘G’, and ‘A’ can appear in the
matrix.

Then the n*m matrix follows.
The input ends with a line of ‘0 0’.

Output

For each test case:
For each kind of tone shown in the matrix, calculate the appearing times of it, and print the
result in descending order according to the appearing times. If more than one kind of tones has
the same appearing times, print them in the lexicographical order.

1
2
3
4
5
6
7
8
9
10
11
12
13
Sample Input
4 5
AGCDE
AGDDE
DDDDD
EEEEE
2 4
GADC
CDEE
0 0
Sample Output
D 8 E 7 A 2 G 2 C 1
C 2 D 2 E 2 A 1 G 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
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
import java.util.Scanner;
import java.io.*;

public class No1 {
    public static void main(String[] args){
    	class chrr{
    		char x;
    		int num;
    	}
        int a = 0, b = 0;
        String cc = null;
        int A = 0, C = 0, D = 0, E = 0, G = 0;
        Scanner scan = new Scanner(System.in);
        while(true)
        {
        	a = scan.nextInt();
            b = scan.nextInt();
        	if(a == 0 && b == 0)
        		break;
        	for(int i=0; i<5; i++)
        	{
        		A = C = D = E = G = 0;
        	}
        	
        	for(int i=0; i<a; i++)
        	{
        			cc = scan.next();
	        		char[] c = cc.toCharArray();
	        		for(int j=0; j<b; j++)
		        	{
	        			if(c[j] == 'A')
	        				A++;
	        			else if(c[j] == 'C')
	        				C++;
	        			else if(c[j] == 'D')
	        				D++;
	        			else if(c[j] == 'E')
	        				E++;
	        			else if(c[j] == 'G')
	        				G++;
	        		}
        	}
        	chrr allc[] = new chrr[5];
        	for(int i=0; i<5; i++)
        		allc[i] = new chrr();
        	allc[0].x = 'A'; allc[0].num = A;
        	allc[1].x = 'C'; allc[1].num = C;
        	allc[2].x = 'D'; allc[2].num = D;
        	allc[3].x = 'E'; allc[3].num = E;
        	allc[4].x = 'G'; allc[4].num = G;
        	
        	for(int i=0; i<4; i++)
        	{
        		for(int j=0; j<4-i; j++)
        		{
        			if(allc[j].num < allc[j+1].num)
        			{
        				chrr temp = allc[j];
        				allc[j] = allc[j+1];
        				allc[j+1] = temp;
        			}
        			else if(allc[j].num == allc[j+1].num)
        			{
        				if(allc[j].x > allc[j+1].x)
        				{
        					chrr temp = allc[j];
            				allc[j] = allc[j+1];
            				allc[j+1] = temp;
        				}
        			}
        		}
        	}
        	
        	for(int i=0; i<5; i++)
        	{
        		if(allc[i].num != 0)
        			System.out.print(allc[i].x + " " + allc[i].num + " ");
        	}
        	System.out.print("\n");
        }
        scan.close();
    }
}

2.（Reverse Words in a String）(30 Points)

Given a string, you need to write a program to
reverse the order of characters in each word within a sentence while still preserving whitespace
and initial word order.

1
2
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
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
import java.util.Scanner;

public class No2 {
	public static void main(String[] args) {
		String str1 = null;
		Scanner scan = new Scanner(System.in);
		while(scan.hasNextLine()) 
		{
			str1 = scan.nextLine();
			char[] cstr1 = str1.toCharArray();
			int len = str1.length();
			char[] cstr2 = new char[len];
			
			int f1 = 0;
			int f2 = 0;
			int z = 0;
			
			for(int i=0; i<len; i++)
			{
				if(cstr1[i] == ' ')
				{
					cstr2[z++] = ' ';
					f1 = f2 = i+1;
				}
				else
				{
					for(int j=i; j<len; j++)
					{
						if(cstr1[j] == ' ')
						{
							f2 = j-1;
							i = j-1;
							break;
						}
						else if(j == len-1)
						{
							f2 = len-1;
							i = len;
							break;
						}
					}
					for(int j=f2; j>=f1; j--)
					{
						cstr2[z++] = cstr1[j];
					}
					
				}
			}
			
			String str2 = String.valueOf(cstr2);
			System.out.print(str2 + '\n');
		}
		scan.close();
	}
	
}

3. (Maximum Submatrix）(40 Points)

Given an n*n matrix composed of 0 or 1, determine the
top left corner position and the order of the maximum submatrix in which all of element are 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input:
5
1 1 0 1 0
1 0 1 0 1
0 1 1 1 0
0 1 0 0 0
0 1 0 0 1
Output: position: (2,1), order: 3*1
Input:
3
1 0 1
0 1 1
1 0 1
output: position: (0,2), order: 3*1
Input:
4
1 1 1 0
0 1 1 0
1 0 1 1
0 1 1 1
output: position: (0, 2), order: 4*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
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
import java.util.*;

public class No3 {
	public static void main(String[] args)
	{
		int n = 0;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		char [][]mat = new char[n][];
		for(int i=0; i<n; i++)
		{
			mat[i] = new char[n];
		}
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				int rem = scan.nextInt();
				mat[i][j] = (char)('0' + rem);
			}
		}
		Solution ret = new Solution();
		ret.maximalRectangle(mat);
		int xx = ret.getx();
		int yy = ret.gety();
		int mxx = ret.getxx();
		int myy = ret.getyy();
		System.out.println("position: (" + xx + "," +yy +"), order: " + mxx + "*" + myy);
		scan.close();
	}
}

class Solution {
	int x;
	int y;
	int maxx;
	int maxy;
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int columnCount = matrix.length,rowCount = matrix[0].length,max=0;
        int[] count = new int[rowCount];
        for(int i=0;i<columnCount;i++){
            for(int j=0;j<rowCount;j++)
                if (matrix[i][j] == '1') 
                    count[j]++;
                else 
                    count[j]=0;
            for(int j=0;j<rowCount;j++){
                int currentCount = count[j];
                while(currentCount>0){
                    int columnNumber=1;
                    int idxx = 0;
                    int flag = 0;
                    for(int idx=j+1;idx<count.length;idx++)
                        if(currentCount <= count[idx])
                            columnNumber++;
                        else
                        {
                        	idxx = idx;
                        	flag = 1;
                            break;
                        }
                    if(flag == 0)
                    	idxx = count.length;
                    max = Math.max(max,columnNumber*currentCount);
                    if(max == columnNumber*currentCount)
                    {
                    	x = i-currentCount+1;
                    	y = idxx-columnNumber;
                    	maxx = currentCount;
	                    maxy = columnNumber;
                    }
	                currentCount--;
                }
            }
        }
        return max;
    }
    public int getx() {
    	return x;
    }
    public int gety() {
    	return y;
    }
    public int getxx() {
    	return maxx;
    }
    public int getyy() {
    	return maxy;
    }
}

4. Chess

implement a simple chess game

Rules of Chess

Project implementation:

The following is the provided code framework:

1

Experiment

implement all the class methods under the chessmen folder. Note that the chessman classes inherit from a abstract base class Chessman in cn/edu/sysu/jood/core/Chessman.java

For each chessman, you need to complete three functions, which are listed as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
Can chessman move?

@param to destination
@return true if can move
*/
public abstract boolean canGo(Position to);

/*
get path to destination.
if
@param to destination
@return point of path
*/
public abstract List<Position> path(Position to);

/*
Get status of chessman

@return 
*/
public abstract Status status();

  • canGo: Can chessman move? For example, the queen at 1d(row 1, column d)wants to move to 4f, as 4f is not on the diagonal对角线 direction, thus canGo should return false.

  • Path: A list of points that is he path from current position to the target position. For example, the queen at 1d wants to move to 5h, thus the Path function should return 2e 3f 4g.

  • status: Return the status of the chessmen (e.g, King, Queen, Knight…..)

Caution:

Only the simple rules are required, the rules related to chessboard are for later experiment. For example, a rook can move any number of squares along a rank or file but cannot leap over other pieces, in which “move any number of squares along a rank or file “ is simple rule, and”cannot leap over other pieces” is chessboard rule.

Rules:

  • King: The king moves one square in any direction.
  • Queen: The queen moves any number of squares in any direction.
  • Rook: A rook can move any number of squares along a rank or file.
  • Bishop: A bishop can move any number of squares diagonally.
  • Knight: A knight moves to any of the closest squares that are not on the sane rank, file, or diagonal.(Thus the move forms an “L”-shape: two squares vertically and one square horizontally, or two squares horizontally and one square vertically.)
  • Pawn: A pawn can move forward to the unoccupied square immediately in front of it on the sanme file.

Judgement

We will use the Junit framework to test each class of chessmen.

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
//Bishop.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

import java.util.ArrayList;

public class Bishop extends Chessman {

	@Override
    public boolean canGo(Position to) {
		int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        int row = Math.abs(to_row-on_row);
        int col = Math.abs(to_column-on_column);
        if(col == row)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Bishop;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
		int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int abs_row = Math.abs(row_d);
        int row_f = row_d / abs_row;
        int col_f = col_d / abs_row;
        for(int i = 1; i < abs_row; i++)
        	ret.add(new Position(getPosition().row+i*row_f,getPosition().col+i*col_f));
        return ret;
	}

}
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
//King.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class King extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int abs_row = Math.abs(to.row-getPosition().row);
        int abs_col = Math.abs(to.col-getPosition().col);
        if (abs_row<2 && abs_col<2)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.King;
        return ret;
    }

	@Override
	public List<Position> path(Position to) {
		List<Position> ret=new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
	}
}
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
//Knight.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Knight extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int sum = 0;
        int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        sum = (to_row - on_row)*(to_row - on_row) + (to_column - on_column)*(to_column - on_column);
        if(sum == 5)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Knight;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
	}    
}
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
//Pawn.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Pawn extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        if((on_column == to_column) && ((to_row-on_row) == 1))
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Pawn;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
    }
}
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
//Queen.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Queen extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int abs_row = Math.abs(to.row-getPosition().row);
        int abs_col = Math.abs(to.col-getPosition().col);
        if (abs_row == abs_col || abs_row==0 || abs_col==0)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Queen;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
    	List<Position> ret=new ArrayList<Position>();
    	int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        
        if(row_d == 0 || col_d == 0)
        {
        	if(row_d == 0)
            {
            	int num = Math.abs(col_d);
            	col_d = col_d / num;
            	for(int i = 1; i < num; i++)
            		ret.add(new Position(on_row,on_column+i*col_d));
            }
            else
            {
            	int num = Math.abs(row_d);
            	row_d = row_d / num;
            	for(int i = 1; i < num; i++)
            		ret.add(new Position(on_row+i*row_d,on_column));
            }
        }
        else
        {
        	int num=Math.abs(row_d);
            row_d = row_d / num;
            col_d = col_d / num;
            for(int i = 1; i < num; i++)
            	ret.add(new Position(on_row+i*row_d,on_column+i*col_d));
        }
        return ret;
	}
}
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
//Rook.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Rook extends Chessman {

    @Override
    public boolean canGo(Position to) {
    	int row = to.row-getPosition().row;
        int col = to.col-getPosition().col;
        if (row == 0 || col == 0)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Rook;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
    	List<Position> ret=new ArrayList<Position>();
    	int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        if(row_d == 0)
        {
        	int num = Math.abs(col_d);
        	col_d = col_d / num;
        	for(int i = 1; i < num; i++)
        		ret.add(new Position(on_row,on_column+i*col_d));
        }
        else
        {
        	int num = Math.abs(row_d);
        	row_d = row_d / num;
        	for(int i = 1; i < num; i++)
        		ret.add(new Position(on_row+i*row_d,on_column));
        }
        return ret;
	}
}

Posted on | In , |
Words count in article: 382 | Reading time ≈ 1

Java程序

先创建以.java后缀结尾的空文件

编译为.class文件

在java虚拟机（java vm）上执行文件

The Java VM

java虚拟机可以在任何不同操作系统中执行

The Java Platform

  1. JVM
  2. Java API

Welcome to Java!

1
2
3
4
5
public class Welcome{
    public static void main(String[] args){
        System.out.println("Welcome to Java!");
    }
}

1

Implementation of a Bicycle

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
public class Bicycle{
    int cadence = 0;
    int speed = 0;
    int gear = 1;
    Bicycle(){
        cadence = 0;
        speed = 0;
        gear = 1;
    }
    void changeCadence(int newValue)
    {
        cadence = newValue;
    }
    void changeGear(int newValue)
    {
        gear = newValue;
    }
    void speedUp(int increment){
        speed = speed + increment;
    }
    void applyBrakes(int decrement){
        speed = speed - decrement;
    }
    void printStates(){
        System.out.println("cadence:" + cadence + "speed:" + speed + "gear:" + gear);
    }
}

public class BicycleDemo{
    public static void main(String[] args){
        Bicycle bike1 = new Bicycle();
        Bicycle bike2 = new Bicycle();
        bike1.speedUp(10);
        bike1.printStates();
        bike2.changeCadence(50);
        bike2.speedUp(15);
        bike2.printStates();
    }
}

eclipse

使用eclipse来运行java：

在workspace创建新项目

创建新的类class

编写

运行

1

java基础知识pdf

ps:

声明在方法中的变量在使用时必须要初始化;

  • 成员变量(实例变量，属性)

成员变量：（在类中定义， 访问修饰符 修饰符 type name = value）

什么是成员变量？

成员变量就是类中的属性。当new对象的时候，每个对象都有一份属性。一个对象中的属性就是成员变量。

  • 局部变量（本地变量）

局部变量：(修饰符 type name = value)

什么是局部变量？

方法的形式参数以及在方法中定义的变量。

1
2
3
4
5
6
7
public class Welcome{
    int j;
    public static void main(String[] args){
        int i;
        System.out.println("Welcome to Java!");
    }
}

Posted on | In |
Words count in article: 1.1k | Reading time ≈ 6

嵌套过程

不调用其他过程的过程称为叶过程(leaf procedure)。如果所有过程都是叶过程，那么情况就很简单。但是某个过程可以调用其他过程，甚至调用的是自身的“克隆”。在调用非叶过程时使用寄存器需要十分小心。

例如，假设主程序将参数3存入寄存器a0,然后使用jal A调用过程A。再假设过程A通过jal B调用过程B，参数为7，同样存入a0。由于A尚未结束任务，所以在寄存器a0的使用上存在冲突。同样，在寄存器ra保存的返回地址也存在冲突，因为它现在保存着B的返回值。

我们必须采取措施阻止这类问题发生：

一个解决方法是将其他所有必须保存的寄存器压栈，就像将保存寄存器压栈一样。调用者将所有调用后还需的参数寄存器（a1~a3）或临时寄存器（t0~t9）压栈。被调用者将返回地址寄存器(ra)和被调用者使用的保存寄存器（a0~a7）都压栈。栈指针 sp 随这栈中的寄存器个数调整。到返回时，寄存器会从存储器中恢复，栈指针也会随着重新调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>

int factorial(int n);

int main()
{
    int n;
    scanf("%d", &n);
    int res = factorial(n);
    printf("%d\n",res);
    return 0;
}

int factorial(int n)
{
    if (n < 1)  return 1;
    else  return n * factorial(n - 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
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
.data
    prompt1: .asciiz "Enter the number\n"
    prompt2: .asciiz "The factorial of n is:\n"

.text
main:
    # Print prompt1
    li $v0, 4
    la $a0, prompt1
    syscall

    # Read integer
    li $v0, 5
    syscall

    # Call factorial
    move $a0, $v0
    jal factorial
    move $a1, $v0 # save return value to a1

    # Print prompt2
    li $v0, 4
    la $a0, prompt2
    syscall

    # Print result
    li $v0, 1
    move $a0, $a1
    syscall

    # Exit
    li $v0, 10
    syscall

    ## Function int factorial(int n)
    factorial:
        ## YOUR CODE HERE
        addi $sp,$sp,-8            #adjust stack for 2 items
        sw   $ra,4($sp)            #save return address
        sw   $a0,0($sp)            #save the argument n
    
        slti $t0,$a0,1             #if n < 1,then set $t0 as 1
        beq  $t0,$zero,L1          #if equal,then jump L1
                                   #above all,if n >= 1,then jump L1
        #if(n < 1)
        addi $v0,$zero,1            #return 1
        addi $sp,$sp,8              #pop 2 items off stack
        jr   $ra                    #return to caller
        #else
        L1:
            add $a0,$a0,-1          #argument :n - 1
            jal factorial           #call factorial with (n-1)
        
           lw   $a0,0($sp)          #restore argument n
           lw   $ra,4($sp)          #restore address
           addi $sp,$sp,8           #adjust stack pionter
           mul  $v0,$a0,$v0         #return n * factorial(n-1)
           jr   $ra                 #return to caller
    ## END OF YOUR CODE
  #jr $ra
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
###########################################################################
#
#    #include<iostream>
#    using namespace std;
#    int sum(int n) {
#        if (n == 1) {
#            return 1;
#        }
#        return n+sum(n-1);
#    }
#
#    int main() {
#      int n = 10;
#      int result = sum(n);
#      cout << result << endl;
#      return 0;
#    }
#
###########################################################################
.text
.globl main
main:
  # Argument for termination condition is saved in $s1, it is 1.
  addi $s1,$0,1
  # Calculate the sum from 1 to 10, n = 10, it is saved in $a1.
  addi $a1,$0,10

  addi $v0,$0,0

  # jump to funcion int sum(int n)
  jal sum
  # print result
  j result

# function
sum:
  # push
  # adjust stack for 2 items (2 * 4 = 8)
  addi $sp,$sp,-8
  #save return address
  sw $ra,4($sp)
  #save argument
  sw $a1,0($sp)

  # n == 1, calculate sum
  beq $a1,$s1,calculate

  # n ！= 1
  # n = n - 1
  addi $a1,$a1,-1
  # push
  jal sum
  # continue to pop

  # branch
  calculate:
    # load argument
    lw $a1,0($sp)
    # load return address
    lw $ra,4($sp)
    # adjust stack for 2 items (2 * 4 = 8)
    addi $sp,$sp, 8
    # n+sum(n-1)
    add $v0,$a1,$v0

    # continue to pop until return main
    jr $ra


result:
  move $a0,$v0
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall

  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  li $v0, 10                                       # exit
  syscall

.data                                              # statement of data
  change:                                          # name of string
       .asciiz "\n"                                # definition of string
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
###########################################################################
#
#    #include<iostream>
#    using namespace std;
#    int sum(int n) {
#        if (n != 1) {
#            return n+sum(n-1);
#        }
#        return 1;
#    }
#
#    int main() {
#      int n = 10;
#      int result = sum(n);
#      cout << result << endl;
#      return 0;
#    }
#
###########################################################################
.text
.globl main
main:
  # Argument for termination condition is saved in $s1, it is 1.
  addi $s1,$0,1
  # Calculate the sum from 1 to 10, n = 10, it is saved in $a1.
  addi $a1,$0,10

  # jump to funcion int sum(int n)
  jal sum
  # print result
  j result

# function
sum:
  # push
  # adjust stack for 2 items (2 * 4 = 8)
  addi $sp,$sp,-8
  #save return address
  sw $ra,4($sp)
  #save argument
  sw $a1,0($sp)

  # n ！= 1, continue to push
  bne $a1,$s1,push_number_and_calculate

  # n == 1, return 1 (pop)
  addi $v0,$0,1
  addi $sp,$sp,8
  # continue to pop
  jr $ra

  # branch
  push_number_and_calculate:
    # n = n - 1
    addi $a1,$a1,-1
    # push
    jal sum

    # pop 2,3,4,...,10, and calculate n+sum(n-1)
    # load argument
    lw $a1,0($sp)
    # load return address
    lw $ra,4($sp)
    # adjust stack for 2 items (2 * 4 = 8)
    addi $sp,$sp, 8
    # n+sum(n-1)
    add $v0,$a1,$v0

    # continue to pop until return main
    jr $ra


result:
  move $a0,$v0
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall

  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  li $v0, 10                                       # exit
  syscall

.data                                              # statement of data
  change:                                          # name of string
       .asciiz "\n"                                # definition of string

Posted on | In |
Words count in article: 2.6k | Reading time ≈ 13

数据类型和方法：

  • 数据类型：字节，byte占用8bit，halfword占用2byte=16bit，word占用4byte=32bit

  • 一个字符需要一个Byte的空间

  • 一个整数需要1个Word（4Byte）的空间

  • MIPS结构的每条指令长度都是32bit

寄存器：

  • 有32个通用寄存器，用编号$0到$31来表示，也可以用寄存器名字来表示，例如$sp,$t1,$ra
  • 有两个特殊的寄存器Lo、Hi，用来保存乘法/除法的运算结果，这两寄存器不能直接寻址，只能用特殊的置零：mfhi和mflo来aceess其中的内容（mfhi = move from Hi, mflo = more from Lo）
  • 堆栈的增长方向是：从内存的高地址方向，向低地址方向。

1

汇编程序结构框架

数据声明：

以.data 开始，声明了在代码中使用的变量的名字。同时，也在主存RAM中创建了对应的空间。

程序代码：

以.text 开始，这部分包含了由指令构成的程序功能代码。代码以main: 函数开始。main的结束点应该调用exit system call

程序的注释：

使用#符号进行注释，每行以#引导的部分都会被视作注释

一个MIPS汇编程序框架：

1
2
3
4
5
6
7
8
9
10
11
# Comment giving name of program and description of function
# Template.s
# Bare-bones outline of MIPS assembly language program
.data           # variable declarations follow this line 
                # ...

.text           # instructions follow this line 
main:           # indicates start of code(first instruction to execute)
                # ...

# End of program, leave a blank line afterwards to make SPIM happy

编写MIPS汇编程序：

Content：

  • Part1： 数据的声明

  • Part2： 数据的装载和保存（Load/Store指令）

  • Part3： 寻址

  • Part4： 算数运算指令： Arithmetic Instructions

  • Part5： 程序控制指令： Control Instructions

  • Part6： 系统调用和I/O操作（SPIM仿真）

Part1： 数据的声明

格式：

1
name:       storage_type    value(s)

创建一个以name为变量名称，values通常为初始值，storage_type代表存储类型。

注意：变量名后要跟一个冒号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# example

var1:   .word   3  # create a single integer:
                   # variable with initial value 3

array1: .byte   'a','b' # create a 2-element character
                        # array with elements initialized:
                        # to a and b

array2: .space  40  # allocate 40 consecutive bytes,
                    # with storage uninitialized
                    # could be used as a 40-element
                    # character array, or a 
                    # 10-element integer array;
                    # a comment should indicate it.
    
string1 .asciiz "Print this.\n" # declare a string

Part2: 数据的装载和保存（Load/Store指令）

  • 主存RAM的存取access只能用load/store指令来完成。
  • 所有其他的指令都使用的是存储器作为操作数。
  1. load指令：
1
2
3
4
5
6
7
8
9
10
11
lw          register_destination, RAM_source    
                    # copy word (4 bytes) at source_RAM location to destination register
                    # load word -> lw

lb          register_destination, RAM_source
                    # copy byte at source RAM location to low-order byte of destination register, and sign -e.g. tend to higher-order bytes
                    # load byte -> lb

li          register_destination, value
                    # load immediate value into destination register
                    # load immediate -> li
  1. store 指令：
1
2
3
4
5
sw          register_source, RAM_destination
                        # store word in source register into RAM destination

sb         register_source, RAM_destination
                        # store byte (low-order) in source register into RAM destination

example:

1
2
3
4
5
6
7
8
9
10
11
12
.data
var1:       .word   23      # declare storage for var1; initial value is 23

.text
__start:
lw          $t0, var1       # load contents of RAM location into register $t0;
                            # $t0 = var1

li          $t1, 5          # $t1 = 5   ("load immediate")
sw          $t1, var1       # store contents of register $t1 into RAM:
                            # var1 = $t1 done
done

Part3: 寻址

MIPS系统结构只能用load/store相关指令来实现寻址操作，包括三种寻址方式：

  • 装载地址： load address，相当于直接寻址，把数据地址直接载入寄存器。
  • 间接寻址： indirect addressing，间接寻址，把寄存器内容作为地址。
  • 基线寻址/索引寻址： based or indexed addressing， 相对寻址， 利用补偿值(offset)寻址
  1. 直接寻址/装载地址：load address:
    1
    la      $t0, var1

把var1在主存RAM中的地址拷贝到寄存器t0中，var1也可以是程序中定义的一个子程序标签的地址。

  1. 间接寻址： indirect addressing：
    1
    lw      $t2, ($t0)

主存中有一个字的地址存在t0中，按这个地址找到那个字，把字拷贝到寄存器t2中。

1
sw      $t2, ($to)

把t2中的字存入t0中的地址指向的主存位置。

  1. 基线寻址/索引寻址： based or indexed addressing：
    1
    lw      $t2, 4($t0)

把t0中地址+4所得的地址所对应的主存中的字载入寄存器t2中，4为包含在t0中的地址的偏移量。

1
sw      $t2, -12($t0)   # offset can be negative

把t2中的内容存入t0中的地址-12所得的地址所对应的主存。

基线寻址在以下场合特别有用：
1、 数组： 从基址出发，通过使用偏移量，存取数组元素。
2、 堆栈： 利用从堆栈指针或者框架指针的偏移量来存取元素。

example：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.data
array1:     .space 12   # declare 12 bytes of storage to hold array of 3 integers

.text
__start:
la          $t0, array1      # load base address of array into register $t0
li          $t1, 5          # $t1 = 5 ("load immediate")
sw          $t1, ($t0)      # first array element set to 5;
                            # indirect addressing
li          $t1, 13         # $t1 = 13
sw          $t1, 4($t0)     # second array element set to 13

li          $t1, -7         # $t1 = -7
sw          $t1, 8($t0)     # third array element set to -7

done

四位四位地走
存入一个字，占用4个字节，消耗4个内存号。且地址偏移量可正可负

Part5 算术运算指令： Arithmetic Instructions

  • 算术运算指令地所有操作数都是寄存器，不能直接使用RAM地址或间接寻址。
  • 操作数地大小都为Word（4-Byte）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
add     $t0,$t1,$t2         # $t0 = $t1 + $t2; add as signed
                            # (2's complement) integers
sub     $t2,$t3,$t4         # $t2 = $t3 - $t4
addi    $t2,$t3, 5          # $t2 = $t3 + 5; "add immediate"
                            # (no sub immediate)
addu    $t1,$t6,$t7         # $t1 = $t6 + $t7;
addu    $t1,$t6,5           # $t1 = $t6 + 5;
                            # add as unsigned intergers
subu    $t1,$t6,$t7         # $t1 = $t6 - $t7;
subu    $t1,$t6,5           # $t1 = $t6 - 5;
                            # subtract as unsigned intergers                  

mult    $t3,$t4             # multiply 32-bit quantities in $t3 and $4,
                            # and store 64-bit result in special registers Lo and Hi: (Hi, Lo) = $t3 * $t4

div     $t5,$t6             # Lo = $t5 / $t6    (integer quotient)
                            # Hi = $t5 mod $t6 (remainder)
mfhi    $t0                 # move quantity in special register Hi to $t0: 
                            # $t0= Hi
mflo    $t1                 # move quantity in special register Lo to $t1:
                            # $t1 = Lo, used to get at result of product or quotient

more    $t2,$t3             # $t2 = $t3

Part6: 程序控制指令： Control Instructions

  1. 分支指令（Branches）

条件分支的比较机制已经内建在指令中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
b           target # unconditional branch to program label target

beq     $t0,$t1,target  # branch to target if $t0 = $t1
blt     $t0,$t1,target  # branch to target if $t0 < $t1
ble     $t0,$t1,target  # branch to target if $t0 <= $t1
bgt     $t0,$t1,target  # branch to target if $t0 > $t1
bge     $t0,$t1,target  # branch to target if $t0 >= $t1
bne     $t0,$t1,target  # branch to target if $t0 <> $t1

beqz     $t0, lab  # branch to lab if $t0 = 0.
bnez     $t0, lab  # branch to lab if $t0 != 0.
bgez     $t0, lab  # branch to lab if $t0 >= 0.
bgtz     $t0, lab  # branch to lab if $t0 > 0.
blez     $t0, lab  # branch to lab if $t0 <= 0.
bltz     $t0, lab  # branch to lab if $t0 < 0.

bgezal  $t0, lab # if $t0 >= 0, then put the address of the next instruction into $ra and branch to lab
bgtzal  $t0, lab # if $t0 > 0, then put the address of the next instruction into $ra and branch to lab
bltzal  $t0, lab # if $t0 < 0, then put the address of the next instruction into $ra and branch to lab

  1. 跳转指令（Jumps）

    1
    2
    j       target  # unconditional jump to program label target
    jr      $t3     # jump to address contained in $t3 ("jump register")

  2. 子程序调用指令

子程序调用指令的实质是跳转并链接（Jump and Link），它把当前程序计数器的值保留到$ra中，以备跳回）

跳到子程序：

1
jal     sub_label       # "jump and link", preserve pc to $ra

sub_label为子程序的标签，如LOOP，SUB_ROUTINE

从子程序返回:

1
jr      $ra     # "jump register" jump as the value of $ra

返回到$ra中储存的返回地址对应的位置，$ra中的返回地址由jal指令保存

注意，返回地址存放在$ra寄存器中，如果子程序调用了下一级程序，或者递归调用，此时需要将返回地址保存在堆栈中，因为没执行依次jal指令就会覆盖$ra中的返回地址。

Part6：系统调用和I/O操作（SPIM仿真）

系统调用是指调用操作系统的特定子程序

系统调用用来在仿真器的窗口中打印或者读入字符串string，并可显示程序是否结束

用syscall指令进行对系统子程序的调用

本操作首先支持$v0 and $a0-$a1中的相对值

调用以后的返回值（如果存在）会保存在$v0中。

1

e.g.

1
2
3
4
# 打印在$t2中的整数
li  $v0, 1
move    $a0, $t2
syscall

1
2
3
4
5
# read integer value, store in RAM location with label int_value (presumably declared in data section)
li      $v0, 5
syscall

sw      $v0, int_value
1
2
3
4
5
6
7
8
9
# print out string
.data
	string1:    .asciiz  "print this.\n"

.text
main:
    li   $v0, 4
    la   $a0, string1
    syscall
1
2
3
# to indicate end of program, use exit system call
li      $v0, 10
syscall

阶乘：

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
.data     
    msg: .asciiz"Enter a Number "
    msg1: .asciiz"The result is: "

.text                   
main:                    
    li $v0,4             
    la $a0,msg           
    syscall  

    li $v0,5              
    syscall  

    move $s0,$v0          
    li $s7, 1      

factorial:              
    mult $s0,$s7        
    mflo $s7     
    sub $s0,$s0,1         
    bgt $s0,1,factorial   

done:
    li $v0,4
    la $a0,msg1
    syscall

    move $a0,$s7         
    li $v0,1              
    syscall          

    li     $v0, 10           
    syscall

冒泡排序：

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
.data
	Array: .word 21,4,12,6,89,17,33,10,9,51
	seperate:.asciiz " "

# for i(0~n-1)
# 	for j(0~n-i)

.text
main:
	la $t6,Array     # t6 = a[0]
    move $t7,$zero   # t7 = 0
    li $t8,10        # t8 = 10 (size)
    move $t9,$zero   # t9 = 0

loop1:
    move $t9,$zero   # t9 = 0

loop2:
	move $t0,$t9     # t0 = t9
    mul $t0,$t0,4	 # t0 = 4*t9
    addu $t1,$t0,$t6   
    lw $t2,0($t1)   # t2 = a[t9]

	addi $t0,$t9,1   # t0 = t9 + 1
    mul $t0,$t0,4
    addu $t4,$t0,$t6
    lw $t3,0($t4)	# t3 = a[t9+1]

    bge $t2,$t3,skip # if(t2 >= t3) goto skip
    sw $t3,0($t1)  # if(t2 < t3) swap
    sw $t2,0($t4)

skip:
   addi $t9,$t9,1   # t9++
   addi $t0,$t9,1   # t0 = t9 + 1
   sub $t1,$t8,$t7    # t1 = t8 - t7
   blt $t0,$t1,loop2  
   addi $t7,$t7,1     
   sub $t2,$t8,1
   blt $t7,$t2,loop1

set:
	move $t7,$zero
	
done:
	move $t0,$t7
   	mul $t0,$t0,4
   	addu $t1,$t0,$t6
   	lw $a0,0($t1)
  	li $v0,1
   	syscall

   	la $a0,seperate  
   	li $v0,4
   	syscall

   	addi $t7,$t7,1
   	blt $t7,10,done

函数调用

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
.text
.globl main
main:
	addi $a1, $0, 2
	addi $a2, $0, 3

	jal print_two_number
	jal addfunction
	j result

addfunction:
	add $v1, $a1, $a2
	jr $ra

print_two_number:
	move $a0, $a1
	li $v0, 1
	syscall
	la $a0, change
	li $v0, 4
	syscall

	move $a0, $a2
	li $v0, 1
	syscall
	la $a0, change
	li $v0 4
	syscall

	jr $ra

result:
	move $a0, $v1
	li $v0, 1
	syscall

	la $a0, change
	li $v0, 4
	syscall

	li $v0, 10
	syscall


.data
	change:
		.asciiz "\n"
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
###########################################################################
#
#    #include<iostream>
#    using namespace std;
#    int add(int a, int b) {
#        int sum;
#        sum = a + b;
#        return sum;
#    }
#
#    int main() {
#      int a = 2;
#      int b = 3;
#      int sum = add(a,b)
#      cout << sum << endl;
#      return 0;
#    }
#
###########################################################################
.text
.globl main
main:
  addi $a1,$0,2                             # $a1: the register to save 2, parameters are stored in registers $a0 - $a3
  addi $a2,$0,3                             # $a2: the register to save 3

  jal print_two_number                      # print two immediates
  jal addfunction                           # jump to a function addfunction
  j result                                  # print result

addfunction:                                # add function
  add $v1,$a1,$a2                           # Calculate the sum and save it into $v1, the registers $v0 and $v1 save the return value
  jr $ra                                    # The return address is saved in $ra

print_two_number:
  move $a0,$a1                                     # move the value into $a0
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall
  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  move $a0,$a2
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall
  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  jr $ra

result:
  move $a0,$v1
  li $v0, 1                                        # load appropriate system call code into register $v0
  syscall

  la $a0, change                                   # load address of string "change"
  li $v0, 4                                        # load appropriate system call code into register $v0
  syscall

  li $v0, 10                                       # exit
  syscall

.data                                              # statement of data
  change:                                          # name of string
       .asciiz "\n"                                # definition of string

Posted on | In |
Words count in article: 1.3k | Reading time ≈ 5

给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。

例如：
N = 2， 写下1，2.这样就只有一个“1”。
N = 12， 我们就会写下1，2，3，4，5，6，7，8，9，10，11，12。这样，1的个数是5。

问题：

  1. 写一个函数f(N)，返回1到N之间出现的“1”的个数，比如f(12) = 5;
  2. 满足条件“f(N) = N”的最大的N是多少？

问题一

解法一：

遍历1到N，将每一个数中含有1的个数加起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ULONGLONG Count1InAInteger(ULONGLONG n)
{
    ULONGLONG iNum = 0;
    while(n != 0)
    {
        iNum += (n % 10 == 1) ? 1 : 0;
        n /= 10;
    }
    return iNum;
}

ULONGLONG f(ULONGLONG n)
{
    ULONGLONG iCount = 0;
    for(ULONGLONG i = 1; i <= n; i++)
    {
        iCount += Count1InAInteger(i);
    }
    return iCount;
}

然而这个算法的时间复杂度是O(N*lgN)

当给定的N比较大时候，运算时间就会很长。

要提高效率，必须摒弃遍历的方法。

解法二：

先从一些简单的情况开始观察：

先看1位数的情况：

如果N >= 1， 那么f(N)都等于1，如果N = 0，则f(N)为0

再看2位数的情况：

如果N的个位数大于等于1，则个位数出现1的次数为十位数的数字加1，如果N的个位数为0，则个位出现1的次数等于十位数的数字。

而十位数上出现1的次数也类似：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，如果十位数大于1，则十位数上出现1的次数为10

接着看3位数的情况：

如果 N = 123;
个位出现1的个数为13；
十位出现1的个数为20；
百位出现1的个数为24；

f(123) = 13 + 20 + 24 = 57;

推导一般情况

假设N = abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字，如果要计算百位上出现1的次数，它将受到三个因素的影响，百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。

如果百位上的数字为0，可知，百位上可能出现1的次数由更高位决定，比如12013，百位出现1的情况可能是100~199、1100~1199、2100~2199、、、11100~11199，一共1200个，也就是由更高位数字（12）决定，并且等于更高位数字12*当前位数100。

如果百位上数字为1，可知百位上可能出现1的次数不仅受到更高位影响，还受低位影响，例如12113，受更高位影响，百位出现1的情况是100~199，1100~1199，。。。，11100~11199，一共1200个，等于更高位数字12*当前位数100.但是它还受低位影响，百位出现1的情况是12100~12113，一共14个，等于低位数13+1

如果百位上的数字大于1即2~9，则百位上可能出现1的次数也仅由更高位决定，比如12213，则百位储下你的可能性为100~199、1100~1199、2100~2199、、、11100~11199，12100~12199，一共1300个，并且等于更高位数字加1，再乘以当前位数，即（12+1）*100

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
LONGLONG Sum1s(ULONGLONG n)
{
    ULONGLONG iCount = 0;
    ULONGLONG iFactor = 1;
    ULONGLONG iLowerNum = 0;
    ULONGLONG iCurrNum = 0;
    ULONGLONG iHigherNum = 0;

    while(n / iFactor != 0)
    {
        iLowerNum = n - (n / iFactor) * iFactor;
        iCurrNum = (n / iFactor) % 10;
        iHigherNum = n / (iFactor * 10);

        switch(iCurrNum)
        {
            case 0:
                iCount += iHigherNum * iFactor;
                break;
            case 1:
                iCount += iHigherNum * iFactor + iLowerNum + 1;
                break;
            default:
                iCount += (iHigherNum + 1) * iFactor;
                break;
        }
        iFactor *= 10;
    }
    return iCount;
}

这个算法，输入长度位Len的数字，时间复杂度为O(Len)，即O(lnn/ln10 + 1)

问题二解法：

要确定最大的数N，满足f(N) = N。

通过上面的算法，可以算得到：

9以下为： 1个

99以下： 20个

999以下：300个

9999以下：4000个

。。。

999999999以下：900000000个

9999999999以下：10000000000个

归纳得到：

f(10^n-1) = n*10^(n-1)。

通过这个递推式，很容易看到，当n = 10^10-1时，f(n)的值大于n，我们可以猜想，当n大于某一个数N时，f(n)会始终比n大，也就是说，最大满足条件在0~N之间，即N是最大满足条件f(n) = n的一个上界。如果能估计出这个N，那么只要让n从N往0递减，每个分别检查是否由f(n) = n，第一个满足条件的数就是我们要求的整数。

因此，问题转化为如何证明上界N确实存在，并估计出这个上界N。

数学归纳法证明得N = 10^11

计算这个最大整数n

令N = 10^11-1 = 99 999 999 999, 让n从N往0递减，依次检查是否有f(n) = n, 第一个满足条件得就是我们要求的整数。

得出n = 1 111 111 110 是满足的最大整数。

扩展问题

对于其他进制表达方式，也可以试一试，看看有什么规律，例如二进制。

暴力遍历？

1 -》1 -》 1

10 -》0+1*2-》2

11 -》1+1*3-》4

100 -》0+1+1*2*2-》5

101 -》1+1+1*2*2-》6