京东2019实习笔试编程题-红黑石头搭建石头塔

编程题描述

有红色和绿色两种颜色的石头,可以用来搭建塔,规定第1层需要1块石头,第i层需要i块石头…求满足最大层数的种类数。

输入描述

输入两个数据,表示红色和绿色石头的个数

输出描述

输出可以组成最大层数的种类数 (输出对1000007取模)

输入样例

4 6
2 1

输出样例

2
1

设计思路

类似于一个变形的背包问题,同时有两个背包。采用递归的方式,每种石头可以放或者不放。

C++程序

#include<list>  
#include<iostream>
#include<vector>
using namespace std;
long long counts = 0;
const int cx = 10000007;
int max = 0;
vector<int>greenValues;
vector<int>redValues;
void methods_maxnums(int green, int red, int floor)//第一次递归函数,计算出能够到达的最大的层数
{

    if (green <= 0 || red <= 0)
    {
        if (floor >= max)
        {
            max = floor;
        }
        else;

        return ;
    }
    //结束条件,
    //先放绿的再看红的
    if ((green-floor) > 0) {

        greenValues.push_back(floor);      //01背包问题  

        methods_maxnums(green - floor, red, ++floor);   //先放绿色

        greenValues.pop_back();  //拿出绿色,选择红色;
        floor--;
    }
    if ((red - floor) > 0) {

        redValues.push_back(floor);      //01背包问题  
        methods_maxnums(green, red - floor, ++floor);     //不放,放红的
    }
}
int methods_nums(int green, int red, int floor)//与上个递归函数类似,作用是计算出满足最大层数的种类数
{
    if (green <= 0 || red <= 0)
    {
        if (floor >= max)
        {
            counts++;
        }
        else;

        return counts;
    }
    //结束条件,
    //先放绿的再看红的
    if ((green - floor) > 0) {
        greenValues.push_back(floor);      //01背包问题  

        methods_nums(green - floor, red, ++floor);   //先放绿色

        greenValues.pop_back();  //拿出绿色,选择红色;
        floor--;
    }

    if ((red - floor) > 0) {

        redValues.push_back(floor);      //01背包问题  
        methods_nums(green, red - floor, ++floor);     //不放,放红的
    }
}
int main()
{
    int red = 1;
    int green = 2;
    int ans = 0;
    // int count = 0;
    // int max = 0;
     cin >> red;  
     cin >> green;  
    methods_maxnums(green, red, 1);
    ans = methods_nums(green, red, 1);
    //cout << "maxfloor" << endl;//调试用输出 计算出最大的层数
    //cout << max << endl;
    //cout << "counts" << endl; //调试用输出 代表输出种类数
    cout << counts << endl;

    //调试用输出,注释掉
    //cout << "redValues" << endl;
    //for (int i = 0; i < redValues.size(); i++)
    //    cout << redValues[i] << endl;
    //cout << "redValues" << endl;
    //cout << redValues.size() << endl;

    return 0;
}

输出如下图所示,为了方便看,我将代码改成for循环形式,注意输出要取模,这里没有。
1
这是我找到的几组输入对应输出。