经典回溯算法问题:九宫格

蓝飞 蓝飞 | 时间:2012-12-18, Tue | 9,635 views
编程算法 

九宫格是在81个格子中,要满足以下条件:(1)每个横行和竖列中的9个格子都包含数字1至9,不重复;(2)每个黑色粗实线围住的9个格子都包含数字1至9,不重复。如下表所示:

7 6 1 9 3 4 8 2 5
3 5 4 6 2 8 1 9 7
9 2 8 1 5 7 6 3 4
2 1 9 5 4 6 3 7 8
4 8 3 2 7 9 5 1 6
5 7 6 3 8 1 9 4 2
1 9 5 7 6 2 4 8 3
8 3 2 4 9 5 7 6 1
6 4 7 8 1 3 2 5 9

要求找出给定数字的九宫格。

【输入形式】

输入9行9列81个数字,其中0表示要填的数字。

【输出形式】

输出满足条件的九宫格。

【输入样例】

0 6 1 0 3 0 0 2 0
0 5 0 0 0 8 1 0 7
0 0 0 0 0 7 0 3 4
0 0 9 0 0 6 0 7 8
0 0 3 2 0 9 5 0 0
5 7 0 3 0 0 9 0 0
1 9 0 7 0 0 0 0 0
8 0 2 4 0 0 0 6 0
0 4 0 0 1 0 2 5 0

【输出样例】

7 6 1 9 3 4 8 2 5
3 5 4 6 2 8 1 9 7
9 2 8 1 5 7 6 3 4
2 1 9 5 4 6 3 7 8
4 8 3 2 7 9 5 1 6
5 7 6 3 8 1 9 4 2
1 9 5 7 6 2 4 8 3
8 3 2 4 9 5 7 6 1
6 4 7 8 1 3 2 5 9

代码及思路如下:

#include<stdio.h>

bool canFill(int a[9][9], int k, int n){
	int i, j, row = k / 9, col = k % 9;
	for(i = 0; i < 9; ++i){
		if(a[i][col] == n){
			return false;
		}
	}
	for(j = 0; j < 9; ++j){
		if(a[row][j] == n){
			return false;
		}
	}
	for(i = row - row % 3; i < row - row % 3 + 3; ++i){
		for(j = col - col % 3; j < col - col % 3 + 3; ++j){
			if(a[i][j] == n){
				return false;
			}
		}
	}
	return true;
}

void fill(int a[9][9], int k = 0){
	int i, j;
	if(k == 81){
		for(i = 0; i < 9; ++i){
			for(j = 0; j < 9; ++j){
				printf("%d ", a[i][j]);
			}
			printf("\n");
		}
		return;
	}
	int row = k / 9, col = k % 9;
	if(a[row][col] == 0){
		for(i = 1; i <= 9; ++i){
			if(canFill(a, k, i)){
				a[row][col] = i;
				fill(a, k + 1);
				a[row][col] = 0;
			}
		}
	}else{
		fill(a, k + 1);
	}
}

int main(){
	int i, j, a[9][9];
	for(i = 0; i < 9; ++i){
		for(j = 0; j < 9; ++j){
			scanf("%d", &a[i][j]);
		}
	}
	fill(a);
	return 0;
}

2013年5月4日3点温习重写代码如下:

#include<stdio.h>

int square[9][9];

int isEnabled(int k, int num){
	int row = k / 9;
	int col = k % 9;
	for(int i = 0; i < 9; ++i){
		if(square[row][i] == num || square[i][col] == num){
			return false;
		}
	}
	int m = row - row % 3;
	int n = col - col % 3;
	for(int i = m; i < m + 3; ++i){
		for(int j = n; j < n + 3; ++j){
			if(square[i][j] == num){
				return false;
			}
		}
	}
	return true;
}

void fill(int k = 0){
	int row = k / 9;
	int col = k % 9;
	if(k >= 81){
		for(int i = 0; i < 9; ++i){
			for(int j = 0; j < 9; ++j){
				printf("%d ", square[i][j]);
			}
			printf("\n");
		}
		return;
	}
	if(square[row][col] > 0){
		fill(k + 1);
		return;
	}
	for(int i = 1; i <= 9; ++i){
		if(isEnabled(k, i)){
			square[row][col] = i;
			fill(k + 1);
			square[row][col] = 0;
		}
	}
}

int main(){
	for(int i = 0; i < 9; ++i){
		for(int j = 0; j < 9; ++j){
			scanf("%d", &square[i][j]);
		}
	}
	fill();
	return 0;
}

经典算法:整数划分问题

蓝飞 蓝飞 | 时间:2012-12-12, Wed | 15,287 views
编程算法 

整数划分问题(算法分析与设计 P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:

6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1

(阅读全文…)

[小技巧]如何得到C语言中int最大值

蓝飞 蓝飞 | 时间:2012-10-29, Mon | 14,282 views
编程算法 

只需一小句代码,如下:

printf("%d\n", ~(unsigned int)0 / 2);

分析:

当无符号0以二进制储存在内存中的时候,每一位都为0,以32位int为例,(unsigned int)0的二进制为:

00000000000000000000000000000000

按位取反(~)后,变成:

11111111111111111111111111111111

此时的十进制为:

4294967295

除以2(因为int类型中有一半表示负数且比正数多一个)之后为:

2147483647

即为32位int类型最大值。

[数学建模参考资料]判断酿酒葡萄品质的五大指标性物质

蓝飞 蓝飞 | 时间:2012-09-07, Fri | 13,421 views
编程算法 
2012数学建模A题第二小题为“根据酿酒葡萄的理化指标和葡萄酒的质量对这些酿酒葡萄进行分级”,关于酿酒葡萄的分级资料似乎很少,于是转而查询判断酿酒葡萄品质的指标,存档于此,留作第二题参考资料。

糖、酸、单宁、色素和芳香物质是构成酿酒葡萄品质优劣的要素。

水和糖是葡萄的最主要成分,这是葡萄能在酵母作用下发酵成葡萄酒的物质基础。酒精是葡萄果实中的糖发酵后的产物。在目前的发酵工艺下,约17克左右的糖,会使每1升的葡萄汁发酵后升高1%的酒精含量。因此,葡萄果实中糖的成份多少,是制约发酵后葡萄酒的酒精度的要素。

(阅读全文…)