九九乘法表、堆排序和八皇后问题

实验内容

  • 编程输出九九乘法表
  • 编程实现堆排序
  • 编程实现解八皇后问题

我的代码

九九乘法表

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
include irvine32.inc
.data

.code
main proc
	call print

	exit
main endp

;call print
;return nothing
print proc
	push ebp
	mov ebp,esp
	pushad

	mov esi,1	;esi=i
	again_1:
		cmp esi,9
		jg final
		mov edi,1;edi=j
		again_2:
			cmp edi,esi
			jg next
			mov eax,esi
			call writedec
			mov al,'*'
			call writechar
			mov eax,edi
			call writedec
			mov al,'='
			call writechar
			mov eax,edi
			mul esi
			call writedec
			push eax
			call printblank
			inc edi
			jmp again_2
		next:
		call crlf
		inc esi
		jmp again_1
	final:
	popad
	pop ebp

	ret
print endp

;push x
;call printblank
;return nohing
printblank proc
	push ebp
	mov ebp,esp
	pushad
	
	mov al,' '
	call writechar
	mov eax,[ebp+8]
	mov ebx,10
	mov edx,0
	div ebx
	cmp eax,0
	jg final
	mov al,' '
	call writechar
	final:
	popad
	pop ebp

	ret 4
printblank endp

end main

/*
输出格式:
1X1=1 
2X1=2 2X2=4 
3X1=3 3X2=6  3X3=9 
9X1=9 9X2=18 9X3=27 …. 9X9=81
#include <stdio.h>
int main(){
    int i,j,n;
    for(i=1;i<=9;i++){
        for(j=1;j<=i;j++)
            printf("%d*%d=%2d  ",i,j,i*j); 
        printf("\n");
    }
    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
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
include irvine32.inc
.data
	two dd 2
	arr dd 3,1,5,7,2,4,9,6,10,8
.code
main proc
	push offset arr
	push lengthof arr
	call print

	push offset arr
	push lengthof arr
	call heapsort

	push offset arr
	push lengthof arr
	call print

	exit
main endp

;push offset H
;push s
;push len
;call heapadjust
;return nothing
heapadjust proc
	push ebp
	mov ebp,esp
	sub esp,4
	pushad

	mov edi,[ebp+16];edi=offset H
	mov ebx,[ebp+12];ebx=s
	mov ecx,[ebp+8]	;ecx=len
	mov edx,[edi+4*ebx];edx=tmp=H[s]
	mov [ebp-4],edx	;tmp存放在[ebp-4]中

	mov eax,ebx
	mul two
	inc eax
	mov esi,eax	;esi=child=2s+1
	again:
		cmp esi,ecx
		jge final
		
		;child+1 <length ?
		mov eax,esi
		inc eax
		cmp eax,ecx
		jge next
		;H[child]<H[child+1]?
		mov eax,[edi+eax*4]
		cmp [edi+esi*4],eax
		jge next
		inc esi	;++child
		
		next:
		;H[s]<H[child] ?
		mov eax,[edi+ebx*4]
		cmp eax,[edi+esi*4]
		jge final
		mov eax,[edi+esi*4]
		mov [edi+ebx*4],eax;H[s]=H[child]
		mov ebx,esi	;s = child
		mov eax,ebx
		mul two
		inc eax
		mov esi,eax	;child = 2*s+1

		mov edx,[ebp-4]
		mov [edi+ebx*4],edx
		jmp again

	final:
	push edi
	push ecx
	call print

	popad
	add esp,4
	pop ebp

	ret 12
heapadjust endp

;push offset H
;push len
;call buildheap
;return nohting
buildheap proc
	push ebp
	mov ebp,esp
	pushad
	
	mov edi,[ebp+12];edi=offset H
	mov ecx,[ebp+8]	;ecx=len
	mov eax,ecx
	dec eax
	mov edx,0
	div two
	mov esi,eax	;esi=i=(length-1)/2
	again:
		cmp esi,0
		jl final
		push edi
		push esi
		push ecx
		call heapadjust
		dec esi
		jmp again

	final:
	popad
	pop ebp

	ret 8
buildheap endp

;push offset H
;push len
;call heapsort
;return nothing
heapsort proc
	push ebp
	mov ebp,esp
	pushad

	mov edi,[ebp+12];edi=offset H
	mov ecx,[ebp+8] ;ecx=len
	push edi
	push ecx
	call buildheap
	mov esi,ecx
	dec esi	;esi=i=length-1
	again:
		cmp esi,0
		jle final
		mov ebx,[edi+esi*4];ebx=tmp=H[i]
		mov eax,[edi+0]
		mov [edi+esi*4],eax	;H[i]=H[0]
		mov [edi+0],ebx		;H[0]=temp
		push edi
		push 0
		push esi
		call heapadjust
		dec esi
		jmp again

	final:
	popad
	pop ebp

	ret 8
heapsort endp

;push offset arr
;push len
;call print
;return nothing
print proc
	push ebp
	mov ebp,esp
	pushad

	mov ebx,[ebp+12]
	mov esi,0
	again:
		cmp esi,[ebp+8]
		jge final
		mov eax,[ebx+4*esi]
		call writedec
		mov al,' '
		call writechar
		inc esi
		jmp again

	final:
	call crlf
	popad
	pop ebp

	ret 8
print endp

end main

/**
堆排序（Heap Sort）
算法思想：
堆的概念
堆：本质是一种数组对象。特别重要的一点性质：
任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆：
大顶堆要求节点的元素都要大于其孩子。
小顶堆要求节点元素都小于其左右孩子。
两者对左右孩子的大小关系不做任何要求。
利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，通过大顶堆来实现。

基本思想：堆排序可以按照以下步骤来完成：
1.首先将序列构建称为大顶堆；（这样满足了大顶堆那条性质：
位于根节点的元素一定是当前序列的最大值）
2. 取出当前大顶堆的根节点，将其与序列末尾元素进行交换；
（此时：序列末尾的元素为已排序的最大值；由于交换了元素，
当前位于根节点的堆并不一定满足大顶堆的性质）
3. 对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质；
4. 重复2.3步骤，直至堆中只有1个元素为止

下面是基于大顶堆的堆排序算法代码：

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<" ";
}
cout<<endl;
}

/**
已知H[s…m]除了H[s] 外均满足堆的定义
调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
@param H是待调整的堆数组
@param s是待调整的数组元素的位置
@param length是数组的长度
**/
/*
void HeapAdjust(int H[],int s, int length)
{
	int tmp = H[s];
	int child = 2s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
	while (child < length) {
		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
			++child ;
		}
		if(H[s]<H[child]) { // 如果较大的子结点大于父结点
			H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
			s = child; // 重新设置s ,即待调整的下一个结点的位置
			child = 2*s+1;
		} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
			break;
		}
		H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
	}
	print(H,length);
}
*/
/**
初始堆进行调整
将H[0..length-1]建成堆
调整完之后第一个元素是序列的最小的元素
**/
/*
void BuildingHeap(int H[], int length){
//最后一个有孩子的节点的位置 i= (length -1) / 2
	for (int i = (length -1) / 2 ; i >= 0; --i)
		HeapAdjust(H,i,length);
}
*/
/*堆排序算法*/
/*
void HeapSort(int H[],int length){
	//初始堆
	BuildingHeap(H, length);
	//从最后一个元素开始对序列进行调整
	for (int i = length - 1; i > 0; --i){
	//交换堆顶元素H[0]和堆中最后一个元素
		int temp = H[i];
		H[i] = H[0];
		H[0] = temp;
		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
		HeapAdjust(H,0,i);
	}
}
int main(){
	int H[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(H,10);
	HeapSort(H,10);
	cout<<"结果：";
	print(H,10);

}
*/

八皇后问题

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
include irvine32.inc
.data
	chess	dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,0
		dd 0,0,0,0,0,0,0,04
	;chess dd 64 dup(0)
	a dd  8 dup(1)
	b dd 15 dup(1)
	x dd 15	dup(1)
	sum dd 0
	msg1 db '第',0
	msg2 db '种可能的摆法:',0
	msg3 db	'	',0
	msg4 db '八皇后摆法总数:',0
.code
main proc
	push 0
	call putqueen
	lea edx,msg4
	call writestring
	mov eax,sum
	call writedec

	exit
main endp

;push n
;call putqueen
;return nothing
putqueen proc
	push ebp
	mov ebp,esp
	pushad
	
	mov ecx,[ebp+8]	;ecx=n
	mov ebx,0	;ebx=col
	again:	
		cmp ebx,8
		jge final
		cmp a[ebx*4],0	;a[col]==0?
		jz next
		mov eax,ecx
		add eax,ebx	;n+col
		cmp b[eax*4],0;b[n+col]==0?
		jz next
		mov eax,ecx
		sub eax,ebx
		add eax,7	;eax=n-col+7
		cmp x[eax*4],0;c[n-col+7]==0?
		jz next
		;进入第一个if
		;放置皇后
		mov [x+eax*4],0	;c[n-col+7]=0
		mov eax,ecx
		add eax,ebx	;eax=n+col
		mov [b+eax*4],0	;b[n+col]=0
		mov [a+ebx*4],0	;a[col]=0
		mov eax,ecx
		mov edx,32
		mul edx		;eax=n*8*4
		mov [chess+eax+ebx*4],1	;chess[n][col]=1

		cmp ecx,7
		jnz L1
		inc sum
		lea edx,msg1
		call writestring
		mov eax,sum
		call writedec
		lea edx,msg2
		call writestring
		call crlf
		;打印棋盘
		mov esi,0	;esi=i
		cmp esi,8
		again_1:
			cmp esi,8
			jge L2
			lea edx,msg3
			call writestring
			mov edi,0	;edi=j
			again_2:
				cmp edi,8
				jge next_1
				mov eax,esi
				mov edx,32
				mul edx	;eax=i*8*4
				mov eax,[chess+eax+edi*4]
				call writedec
				mov al,' '
				call writechar
				next_2:
				inc edi
				jmp again_2
			next_1:
			call crlf
			inc esi
			jmp again_1

		L1:
		mov eax,ecx
		inc eax
		push eax
		call putqueen	;递归
		L2:
		;取消皇后
		mov eax,ecx
		mov edx,32
		mul edx	;eax=n*8*4
		mov [chess+eax+ebx*4],0	;chess[n][col]=0
		mov eax,ecx
		add eax,ebx	;eax=n+col
		mov [b+eax*4],1	;b[n+col]=1
		mov eax,ecx
		sub eax,ebx
		add eax,7	;eax=n-col+7
		mov [x+eax*4],1	;c[n-col+7]=1
		mov [a+ebx*4],1	;a[col]=1

		next:
		inc ebx
		jmp again

	final:
	popad
	pop ebp

	ret 4
putqueen endp

end main

/*
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
有人用图论的方法解出92种结果 

算法-C描述
#include<stdio.h>
void PutQueen(int n);
int chess[8][8]={0};
int a[8],b[15],c[15];
int sum=0;

int main(){
	int i;
	for(i=0;i<8;++i)
		a[i]=1;
	for(i=0;i<15;++i){
		b[i]=1;
		c[i]=1;
	}
	PutQueen(0);
	printf("八皇后摆法总数：%d\n", sum);
	return 0;
}

void PutQueen(int n){	//统计所有摆法
	int col,i,j;
	for(col=0;col<8;col++){
		if(a[col]&&b[n+col]&&c[n-col+7]){	//判断安全位置
			chess[n][col]=1;	//放置皇后
			a[col]=0;
			b[n+col]=0;
			c[n-col+7]=0;
			if(n==7){
				sum++;
				printf("第%d种可能的摆法:\n", sum);//输出皇后摆法for(i=0;i<8;i++){
				for(i=0;i<8;i++){
					printf("\t\t");
					for(j=0;j<8;j++)
						printf("%d ", chess[i][j]);
					printf("\n");
				}
				printf("\n"); 
				if(sum%10==0){	//每输出十种暂停
					printf("按回车键继续......");
					getchar();
				}
			}
			else PutQueen(n+1);	//递归
			chess[n][col]=0;	//取消皇后
			b[n+col]=1;
			c[n-col+7]=1;
			a[col]=1;
		}
	}//for循环结束
}
*/

补充文件