寒假之(递归与分治)

2024-04-23 21:08
文章标签 递归 分治 寒假

本文主要是介绍寒假之(递归与分治),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归的思想就把问题简单化,分为更小的子问题,一个一个去解决,每种情况之间还会回溯,分出所有的情况,对于一些数据量小的问题,可以用全递归,对于数据量大的,就可以用DP(记忆化搜索)(现在不提)。穷尽搜索时可以考虑递归算法。具有一定的回退性。

分治与递归是分不开的,将问题分为局部问题。递归求解局部为。将局部问题”整合“,解决原问题。

看道题目:

编写一个程序,读取n个元素和整数m的序列a,如果可以通过在a中添加元素来生成m,则输出“yes”,否则输出“no”。一个元素只能使用一次。              

在每个问题中都包含mi的顺序A和Q问题。              

输入              

在第一行给出n。在第二行中,给出n个整数。第三行中给出了q。然后,在第四行中,给出q整数(mi)。              

输出              

对于每个问题mi,打印“是”或“否” 

Constraints

  • n ≤ 20
  • q ≤ 200
  • 1 ≤ elements in A ≤ 2000
  • 1 ≤ Mi ≤ 2000

Sample Input 1

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

Sample Output 1

no
no
yes
yes
yes
yes
no
no

首先看题,不知道怎么下手,怎么用循环把所有的情况列举出来,再来判断?有点困难,题解用递归实现穷举,将情况全部都判断一遍,递归有个好处,可以回溯返回上一层的情况,接着改变状态,再判断一次,看看能否满足条件。第一个数列的每个数据都有两种状态,可以选,也可以不选。于是,递归的这个方程就是将所有情况都考虑进去,就可以实现穷举所有情况。(需要将所有情况都考虑进去)。

如果选择当前数据,就 当前的满足条件的和(每次递归都会不一样的,状态不一样,类似于状态转移方程,每次的状态都会改变)。

代码就会出来:

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<set>
const int maxn=100005;
typedef long long ll;
int n;
int	a[maxn];
int solve(int i,int m){if(m==0)return 1;if(i>=n)return 0;int res=solve(i+1,m)||solve(i+1,m-a[i]);return res;}
int main()
{int q,m,i;cin>>n;for(i=0;i<n;i++)cin>>a[i];cin>>q;for(i=0;i<q;i++){cin>>m;if(solve(0,m))cout<<"yes"<<endl;elsecout<<"no"<<endl;}return 0;
}

用1来表示被选中,0表示没被选中。solve(i+1,m) || solve(i+1,m-a[i])  是两种状态,可以选,也可不选,穷尽搜索将所有情况考虑进去。

放苹果 POJ 1664 

Description

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

Input

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

Output

对输入的每组数据M和N,用一行输出相应的K。

Sample Input

17 3

Sample Output

8

同样采取 递归穷尽搜索的方法,来得到所有的可能, 这就需要将所有的分的方法都要想到,大致可以分为 1.至少有一个空盘子 2.没有空盘子。如果盘子数量大于苹果的数量,就可以把多余的盘子扔掉(因为没有用)。思路大概是这个样子。  第一种情况,可以有盘子为空的情况,那就在别的盘里面多放几个,盘子数量减减,直到盘子就为一个的时候,这就到达终点了,将所有苹果全放到这一个盘子里面。2.第二种情况就是,没有盘子为空的,所有盘子都有苹果,那就把余下的苹果再按照这几个盘子再去分,就会达到每个盘子数量不一样的情况,直到分的苹果最后为0 的时候,说明苹果一遍一遍的  以一个为单位放到每个盘子情况结束。

因为递归有回溯的功能,这两种情况会不断地重叠,交叉,来达到穷举的效果。

想到这里,代码基本上就会出来了:

代码:

 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
const int maxn=1000100;
using namespace std;
typedef long long ll;
const int mod=1000000000;
ll fun(ll m,ll n)
{if(m==0||n==1)  return 1;if(m<n)fun(m,m);     elsereturn fun(m,n-1)+fun(m-n,n);    
}
int main()
{int t;cin>>t;ll m,n;while(t--){cin>>m>>n;cout<<fun(m,n)<<endl;}return 0;
}

 基本上的思想就是这样子。但是分治与递归的题型会很多。就在训练题中一个一个遇见吧。

递归与分治练习题目 HDU 4643 2050 POJ 2586 

 

 

这篇关于寒假之(递归与分治)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929892

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

【UVA】10651-Pebble Solitaire(直接递归或者记忆化)

不知道这个题UVA的数据是怎么的,用2个方法交了,第一次直接递归,第二次记忆化剪枝,时间竟然一样!? 直接郁闷了,简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

HCIA--实验十:路由的递归特性

递归路由的理解 一、实验内容 1.需求/要求: 使用4台路由器,在AR1和AR4上分别配置一个LOOPBACK接口,根据路由的递归特性,写一系列的静态路由实现让1.1.1.1和4.4.4.4的双向通信。 二、实验过程 1.拓扑图: 2.步骤: (下列命令行可以直接复制在ensp) 1.如拓扑图所示,配置各路由器的基本信息: 各接口的ip地址及子网掩码,给AR1和AR4分别配置

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日,他们俩30岁生日那天,当年

Winform中在窗体中的Paint事件中重绘会导致递归问题?

在 WinForms 应用程序中,如果在窗体的 Paint 事件处理程序中不断调用 Invalidate 方法,确实可能会导致递归调用的问题。这是因为每次调用 Invalidate 方法时,都会向消息队列添加一个绘制消息,当消息队列中的绘制消息被处理时,会触发 Paint 事件。如果 Paint 事件处理程序中又调用了 Invalidate,就会形成一个循环,导致递归调用 Paint 事件,这