补全等式(DFS,全排列)

迈不过友情╰ 2022-06-18 09:14 209阅读 0赞

下图中，每个方块代表 1…13 中的某一个数字，但不重复。  
![这里写图片描述][SouthEast]  
例如：  
1×2+9×7=13×5  
10×8+12×3=11×4  
只要有任意一个方块代表的数字不同，就算两种不同的方案。  
请你计算，一共有多少种不同的方案。

方法一: DFS 速度快  
方法二: 暴力全排列 速度慢

#include <bits/stdc++.h>
    using namespace std;
    bool visit[13];
    int a[12];
    int ans = 0;
    void dfs(int step) {
        if(step == 6) {
            if(a[0]*a[1] + a[2]*a[3] != a[4]*a[5])
                return;
        } else if(step == 12) {
            if(a[6]*a[7] - a[8]*a[9] == a[10]*a[11])
                ans++;
            return;
        }
        for(int i = 0; i < 13; i++) {
            if(visit[i] == false) { //说明i没被使用
                a[step] = i+1;  //放入a[step] 因为从1开始 使用+1 
                visit[i] = true;  //尝试 如果这个数合适就继续dfs
                dfs(step+1);
                visit[i] = false; //不合适就继续 直到找到满意条件的
            }
        } 
        return ;
    } 
    int main()
    {   
        dfs(0);
        cout << ans;
        return 0;
    }

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {   
        int ans = 0;
        int a[13] = {
       1,2,3,4,5,6,7,8,9,10,11,12,13};
        do{
            if(a[0]*a[1] + a[2]*a[3] == a[4]*a[5]
            && a[6]*a[7] - a[8]*a[9] == a[10]*a[11]){
                ans++;
            }
        }while(next_permutation(a,a+13));*/
        cout << ans;
        return 0;
    }

[SouthEast]: /images/20220618/15c1273977ea4f7a86bec21f77c3bb8c.png

发表评论取消回复

表情：

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

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

相关阅读

相关全排列深搜dfs

include<iostream> include<cstdio> using namespace std; int a[100],vis[10

- 日理万妓/ 2024年02月17日 19:26/ 0 赞/ 48 阅读

相关打印全排列（DFS）

> 前言：OJ上一道简单算法题，打印全排列。用深度优先搜索（DFS）来实现，顺便记录一下基础DFS模板。题目描述给定一个正整数n，取出前n小的正整数，即 1~n 这

超、凢脫俗/ 2023年03月01日 08:38/ 0 赞/ 80 阅读

相关全排列——回溯算法+dfs

leetcode.46.全排列——回溯算法+dfs 给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3] 输出:

骑猪看日落/ 2022年12月04日 15:56/ 0 赞/ 220 阅读

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

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

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

相关全排列

问题描述：设有\{r1,r2,...,rn\}共n个元素，这n个元素中可能存在重复元素，试设计一个算法，列出这n个元素的不同排列。参考代码： inclu

电玩女神/ 2022年08月05日 02:54/ 0 赞/ 232 阅读

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

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

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

相关全排列

题目描述给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3] 输出: [ [1,2,3],

以你之姓@/ 2022年04月25日 06:54/ 0 赞/ 249 阅读

相关全排列

全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以\{1, 2, 3, 4, 5\}为例说明如何编写全排列的递归算法。 1、首先看

男娘i/ 2022年03月19日 01:50/ 0 赞/ 293 阅读

相关全排列

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例: 输入："23" 输

约定不等于承诺〃/ 2022年02月15日 00:47/ 0 赞/ 315 阅读

相关全排列

talk is cheap, show me the code. public static void permutation(char[]ss,int i){

蔚落/ 2022年01月29日 04:55/ 0 赞/ 334 阅读