【算法练习 | C】补全等式——（全排列、深度搜索算法）

深碍√TFBOYSˉ_ 2022-12-04 07:54 146阅读 0赞

下图中，每个方块代表  1 … 13 1\\ldots13 1…13 中的某一个数字，但不重复。

![在这里插入图片描述][20200906211422406.png_pic_center]

例如：

1 × 2 + 9 × 7 = 13 × 5 1 \\times 2 + 9 \\times 7 = 13 \\times 5 1×2\+9×7=13×5

10 × 8 − 12 × 3 = 11 × 4 10 \\times 8 - 12 \\times 3 = 11 \\times 4 10×8−12×3=11×4

只要有任意一个方块代表的数字不同，就算两种不同的方案。

请你计算，一共有多少种不同的方案。

**问题说明：** 此问题直接进行全排列运算时间会非常长，因此在使用深度搜索算法时，采取了一些措施。

**答案：** `122368`

#include <stdio.h>
    #define N 13
    
    int a[N];
    int book[N] = { 0};
    int sum=0;
    
    void dfc(int step) { 
    	int i;
    	
    	//如果第一个式子不成立，则无需继续计算 
    	if(step==6) { 
    		if(a[0]*a[1]+a[2]*a[3]!=a[4]*a[5]) { 
    			return;
    		}
    	}
    	
    	if(step==12) { 
    		if(a[6]*a[7]-a[8]*a[9]==a[10]*a[11]){ 
    			sum++;
    		}
    		return;
    	}
    	
    	for(i=0;i<N;i++) { 
    		if(book[i]==0) { 
    			book[i] = 1;
    			a[step] = i+1;
    			dfc(step+1);
    			book[i] = 0;
    		}
    	}
    }
    
    int main() { 
    	dfc(0);
    	printf("%d",sum);
    	return 0;
    }

[20200906211422406.png_pic_center]: /images/20221123/c8652571dec84952bdcf74a884cc0bb2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法练习 | C】补全等式——（全排列、深度搜索算法）

下图中，每个方块代表 1 … 13 1\\ldots13 1…13 中的某一个数字，但不重复。 ![在这里插入图片描述][20200906211422406.png_pic

深碍√TFBOYSˉ_/ 2022年12月04日 07:54/ 0 赞/ 147 阅读

相关【算法练习 | C】九宫格——（全排列、深度搜索算法）

将数字 1 … 9 1 \\ldots 9 1…9 填入一个 3 × 3 3 \\times 3 3×3 的九宫格中，使得格子中每一横行和的值全部相等，每一竖列和的值全部相

妖狐艹你老母/ 2022年12月04日 07:53/ 0 赞/ 90 阅读

相关【算法】全排列

> 该死的入参，偏偏重要的时候与我作对 import java.math.BigInteger; import java.util.Arrays; i

男娘i/ 2022年12月02日 01:04/ 0 赞/ 195 阅读

相关【蓝桥杯】【啊哈！算法】深度优先搜索——全排列

[【啊哈！算法】系列文章目录][Link 1] -------------------- 目录【啊哈！算法】系列文章目录需求介

不念不忘少年蓝@/ 2022年11月17日 14:52/ 0 赞/ 219 阅读

相关数组全排列递归算法C语言,C++全排列递归算法

1、将一个n维数组初始化，第0位填1，第1位填2.。。。。。第n-1位填n； 2、将数组看为两部分，一个是已排好的，剩下是待排的，分别用两个指针指向； 3、将第一个字符，

比眉伴天荒/ 2022年10月14日 15:52/ 0 赞/ 201 阅读

相关全排列算法

1.递归全排列分别将每个位置交换到最前面位，之后全排列剩下的位。递归全排列 1 2 3 4 5 1，for循环将每个位置的数据交换到第一位

爱被打了一巴掌/ 2022年08月06日 00:12/ 0 赞/ 216 阅读

相关补全等式(DFS,全排列)

下图中，每个方块代表 1…13 中的某一个数字，但不重复。 ![这里写图片描述][SouthEast] 例如： 1×2+9×7=13×5 10×8+12×3=1

迈不过友情╰/ 2022年06月18日 09:14/ 0 赞/ 197 阅读

相关 STL：全排列算法

字典法非递归全排列 > 这里解析的是《STL源码剖析》中全排列的算法，属于非递归算法； > 下面我用尽可能简单的语言让读者明白什么是字典法全排列，额外插一句： >

旧城等待，/ 2022年05月21日 00:19/ 0 赞/ 218 阅读

相关全排列算法

一、递归法引用：[https://www.cnblogs.com/mengfanrong/p/3854044.html][https_www.cnblogs.com_men

谁借莪１个温暖的怀抱￠/ 2022年05月14日 07:41/ 0 赞/ 225 阅读

相关数组元素的全排列算法，重复全排列算法，子集求解算法，任意排列算法

输出字符数组的全排列，这个问题利用递归的方式比较简单。数组的重复全排列与全排列的区别主要相当于（有放回还是没有放回）。输出字符数组的所有排列，包括全排列，单个元素，多个元素

我不是女神ヾ/ 2022年05月14日 06:29/ 0 赞/ 282 阅读