算法学习3_枚举
2018-06-15 本文已影响9人
hhjdk
枚举算法又称穷举算法
枚举算法的核心思想 ： 有序的尝试每一种可能
题一、 3 * 6528 = 3 * 8256 ,在空格里面填入两个相同的数字保持等式成立？
这是最简单的枚举算法
for (int i = 0; i < 10; i ++) {
if ((i * 10 + 3)*6528 == (3*10+i)*8256) {
printf("空格填入的数值是: %d \n",i);
}
}
题二、_ _ _ + _ _ _ = _ _ _ ,将1-9 分别填入空格，，每一个数字只可以使用一次，
例如 173 + 286 = 459； ，还有 286 + 173 = 459 和之前的算一种可能，有多少种可能
因为每一个数字只能使用一次使得等式成立，所以我使用一个book[10]数组来标记该数字是否有出现，出现了标记为book[i] = 1，默认为book[i] = 0
下面的 为什么要 total/2，是因为 173 + 286 = 459和 286 + 173 = 459算一种可能
// 这个打印当前时间的一个方法
char* getDateTime()
{
static char nowtime[20];
time_t rawtime;
struct tm* ltime;
time(&rawtime);
ltime = localtime(&rawtime);
strftime(nowtime, 20, "%Y-%m-%d %H:%M:%S", ltime);
return nowtime;
}
int main(int argc, const char * argv[]) {
int a [10], i,total = 0 ,book[10], sum; // a[i] 用来存储 9个数 ，使用book[10] 来存储数字出现的次数
// 因为是 1- 9 ，所以，重1开始计算
char * time = getDateTime();
printf("时间 ====%s \n",time);
// 时间复杂度 O(a^n) 时间复杂度太高
for (a[1] = 1; a[1] < 10 ; a[1]++) {
for (a[2] = 1; a[2] < 10 ; a[2]++) {
for (a[3] = 1; a[3] < 10 ; a[3]++) {
for (a[4] = 1; a[4] < 10 ; a[4]++) {
for (a[5] = 1; a[5] < 10 ; a[5]++) {
for (a[6] = 1; a[6] < 10 ; a[6]++) {
for (a[7] = 1; a[7] < 10 ; a[7]++) {
for (a[8] = 1; a[8] < 10 ; a[8]++) {
for (a[9] = 1; a[9] < 10 ; a[9]++) {
for (i = 1; i < 10; i ++) { // 初始化book数组
book[i] = 0;
}
for (i = 1; i < 10; i ++) {
book[a[i]] = 1;
}
// 统计出现了多少个不同得数
sum = 0;
for (i = 1; i < 10; i ++) {
sum += book[i];
}
// 如果出现了 9个数，并且满足等式 条件，这输出
if (sum == 9 && (a[1]* 100 + a[2] * 10 + a[3]) + (a[4]* 100 + a[5] * 10 + a[6]) ==
(a[7]* 100 + a[8] * 10 + a[9])) {
printf("%d%d%d + %d%d%d = %d%d%d \n" ,a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
total ++;
}
}
}
}
}
}
}
}
}
}
printf("total === %d \n",total/2);
time = getDateTime();
printf("时间 ====%s \n",time);
getchar();
return;
}
题三、 假如你只有一个炸弹，这颗炸弹威力超强，可以炸死范围里面的所有敌人，放在那里，可以炸死更多的敌人
地图模型化
墙有两种，一种可以炸，一种不可以炸，当前只有一颗炸弹，
所以
成墙用 # 表示，炸弹不能穿墙，
敌人用 G 表示，
空地用 . 表示，炸弹只能放在空地上
具体地图模型如下
13 * 13
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.###
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############
分析：首先我们需要一个二维数组来存储这个地图，至于炸弹放在哪个位置炸死的敌人最多，需要一个个尝试，炸弹的爆炸方向是 上下左右 所以，炸弹的爆炸统计如下
假如炸弹在坐标x ,y上，炸弹的涉及范围的坐标变化如下
具体消灭如下所示
(x - 1, y)
(x, y - 1) (x , y) (x, y + 1)
(x + 1, y)
具体demo如下
int main(int argc, const char * argv[]) {
char a[20][20]; // 假设地图大小不超过20*20
int i ,j, sum ,map = 0,p = 0,q = 0,x,y,n,m;
printf("输入,n， m, 代表行和列:");
scanf("%d %d",&n, &m); // n 代表多少行， m代表多少列
printf("n = %d , m = %d \n",n,m);
// 读入n行字符
for (i = 0; i < n; i ++) {
printf("输入该行参数 %d",i);
scanf("%s",a[i]);
}
// 利用两重循环便利枚举里面的每一个点
for (i = 0; i < n; i ++) {
for (j = 0; j < m ; j ++) {
// 首先判断这个点是不是平底，是平底才可以防止炸弹
if (a[i][j] == '.') {
sum = 0; // sum 用来计数（可以消灭的敌人数），所以初始化需要为0
// 将当期坐标 i , j 复制到两个新变量 x , y 中， 以便上下左右四个方向统计可以消灭的敌人数
// 向上统计可以消灭的敌人数
x = i ; y = j; // 这里的坐标不是x,y 代表的意思是 第x行， 第y列
while (a[x][y] != '#') {
if (a[x][y] == 'G') {
sum ++;
}
x --; // x --继续向上统计可以消灭的敌人数
}
// 向下统计可以消灭的敌人数
x = i ; y = j; // 这里的坐标不是x,y 代表的意思是 第x行， 第y列
while (a[x][y] != '#') {
if (a[x][y] == 'G') {
sum ++;
}
x ++; // x ++继续向下统计可以消灭的敌人数
}
// 向左统计可以消灭的敌人数
x = i ; y = j; // 这里的坐标不是x,y 代表的意思是 第x行， 第y列
while (a[x][y] != '#') {
if (a[x][y] == 'G') {
sum ++;
}
y --; //
}
// 向右统计可以消灭的敌人数
x = i ; y = j; // 这里的坐标不是x,y 代表的意思是 第x行， 第y列
while (a[x][y] != '#') {
if (a[x][y] == 'G') {
sum ++;
}
y ++;
}
// 更新map 的值
if (sum > map) {
map = sum;
p = i; // 记录行
q = j; // 记录列
}
}
}
}
printf("炸弹坐标为(%d ,%d)，可以炸死最多的敌人%d \n",p,q,map); // 结果 (9,9) 消灭8 个
getchar();
return;
}
本人也是刚刚学习，如有错误，请多多指正。
本文部分内容参考 【啊哈！算法】这本书
代码例子
