首页 > 其他分享 >回溯法 求幂集 (递归+非递归)

回溯法 求幂集 (递归+非递归)

时间:2023-05-05 21:33:58浏览次数:36  
标签:幂集 递归 int arr state 回溯 op

/*
  回溯法--求幂集(递归+非递归)
 */
#include <cstdio>
const int N = 100;
int n = 3;    ////集合中元素个数
int state[N]; // 递归要用,0:不选,1:选,2:未确定
int op[N];    //非递归要用,0:不选,1:选,2:未确定
/*
  输出数组中的数字
 */
void print_arr(int arr[], int n)
{
    for (int i = 1; i <= n; i++) //检查有没有2,主要是非递归法要用这个循环,递归法不用
        if (arr[i] == 2)
            return;

    for (int i = 1; i <= n; i++)
    {
        if (arr[i] == 1)
        {
            printf("%d ", i);
        }
    }
    puts("");
}
/*
  递归
  u:当前要选择的位置
 */
void dfs(int u)
{
    if (u > n)
    {
        print_arr(state, n);
    }
    else
    {
        state[u] = 0;
        dfs(u + 1);
        // state[u] = 2; //恢复现场,可省略
        state[u] = 1;
        dfs(u + 1);
        // state[u] = 2; //恢复现场,可省略
    }
}
/*
非递归
强行写的,过程上没有怎么优化
其实还是枚举,输出的时候判断下是否存在2(没有确定元素的项),若有则不输出
 */
void BackTrack()
{
    int i = 1;
    while (i >= 1)
    {
        if (i > n)
        {
            print_arr(op, n);
            i--;
        }
        if (op[i] == 2)
        {
            op[i] = 0; // 第i个位置不选
            i++;       // 向下一层前进,扩展分支
        }
        else if (op[i] == 0)
        {
            op[i] = 1; // 重设分支的状态为未定
            i++;       // 向上一层回溯,扩展分支
        }
        else if (op[i] == 1)
        {
            op[i] = 2; // 重设分支的状态为未定
            i--;       // 向上一层回溯,扩展分支
        }
    }
}
int main()
{
    for (int i = 1; i <= n; i++)
    {
        //开始时所有位置未确定
        state[i] = 2;
        op[i] = 2;
    }
    printf("递归求幂集:\n");
    dfs(1);
    printf("非递归求幂集:\n");
    BackTrack();
    return 0;
}

 

标签:幂集,递归,int,arr,state,回溯,op
From: https://www.cnblogs.com/FishSmallWorld/p/17375418.html

相关文章

  • SQL 通用表达式递归查询的应用举例
    前置知识对于大多数人来说,SQL意味着SELECT、INSERT、UPDATE和DELETE。但实际上,SQL能够实现的功能远远不止简单的增删改查;今天我们来介绍一个高级功能:通用表表达式(CommonTableExpression)。CTE可以提高复杂查询的性能和可读性,实现树状结构或者图数据的遍历。例如:生成数字......
  • 可变参数 递归
        ......
  • LeetCode -- 递归 dfs、回溯
    22. 括号生成 classSolution{publicList<String>generateParenthesis(intn){List<String>result=newArrayList();if(n==0){returnresult;}//必须要用字符串,每次拼接要产生新对象。不能用StringBuf......
  • 递归
    当寒月还在读大一的时候,他在一本武林秘籍中发现了神奇的二进制数(秘籍名:计算机基础) 如果一个正整数表示成二进制,它的位数为n(不包含前导0),寒月称它为一个n二进制数,所有的n二进制数中,1的总个数被寒月称为n对应的月之数。 例如,3二进制数总共有4个,分别是4(100)、5(101)、6(110)、7(11......
  • 递归
    一个人写了9封不同的信及相应的9个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种? 若1 2 3 4为正确排列,则所有元素均不在正确位置的排列称之为错排 #include<stdio.h>intmain(){ intn,i;scanf("%d",&n);intf[n+1];f[1]=0;f[2]=1;for(i......
  • 递归
    有2N张牌,编号为1,2,3..n,n+1,..2n,通过一次洗牌可以把牌的序列变为 n+1,1,n+2,2,n+3,3,n+4,4..2n,n可以证明,对于任意自然数N,都可以在经过M次洗牌后第一次重新得到初始的顺序。编程对于小于100000的自然数N,求出M的值。输入:每行一个整数N输出:输出与之对应的M输入样例:201输出样例:......
  • 循环?还是递归?
    前言前几天群里有几个小伙伴,展开了如下讨论:--------------------------------------------------------------------------【西安-Java-小白】    谁遇上过?【杭州-Java-JOEL】    你要打断点看哪行出错......
  • 【web 开发基础】PHP 中的递归函数
    前言什么是递归?递归做为一种算法在程序设计语言中广泛应用。所谓的递归简单地概括就是程序调用自身的编程技巧称为递归(recursion)。递归在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学......
  • 回溯法解决图着色问题
     #include<iostream>usingnamespacestd;intG[50][50];//保存无向图intcolor[50];//存放每个点的颜色intsum=0;//需要的颜色总数intmins=999999;//需要的最少的颜色数intN;//点的总个数//检查点第i+1个点是否能放颜色cboolcheck(inti,......
  • 回溯法解决01背包问题
    #include<iostream>usingnamespacestd;structthing{intweight;//物品重量intvalue;//物品价值intnumber;//物品数量};thingthings[10];//假设最多有10个物品intthingsCount;//物品数量intbagSize;//背包容量intmaxTotalValue;//最大总重量......