C++初学者算法作业

Question

我有一个任务，听起来是这样的:“弓箭手有黑色和白色的箭，他只能用白箭射白鸭子，只能用黑箭射黑鸭子。鸭子成群结队地来，长长的大小是这样的:一只，然后是两只，然后是三只，然后是五只，八只，等等，所以基本上是斐波那契数列。这些组中的鸭子是有序的，这样你就不会在彼此附近找到两只相同颜色的鸭子，每组以一只白鸭开始(例如，对于其中有 5 只鸭子的组:白 黑 白 黑 白)。如果弓箭手能杀死整个组，他只能杀死鸭子。"

鉴于白箭 (ka) 和黑箭 (kb) 的数量，我必须说出弓箭手杀死了多少组，以及他还剩下多少支每种类型的箭。

int ka, kb;
cin >> ka >> kb;

int total_rows{0};
for(int current_group{1}, previous_group{1}; ka+kb >= current_group; ++total_rows)
{
    //see which of the arrows he shoots
    for(int i=1; i <= current_group; ++i)
    {
        if(i%2 == 1)
            --ka;
        else
            --kb;
    }

    // swap the 2 fib numbers so we can get the next one
    swap(current_group, previous_group);

    current_group += previous_group;
}

cout << total_rows << ' ' << ka << ' ' << kb;  

例如，如果我输入 9 和 10，我应该得到 4、2、6。我得到了一些与此无关的东西......

Answer 1

计算将使用多少箭头的方法可能与您正在使用的方法略有不同。正如我们所知，鸭子是交替出现的，这意味着对于奇数组，您将需要额外的白色箭头，否则每种颜色使用的数量将为 N/2

#include <iostream>

int next_group()
{
    static int prev = 0;
    static int next = 1;

    int res = prev + next;
    prev = next;
    next = res;

    return next;
}

int main()
{
    int white, black;
    std::cin >> white >> black;

    int groups = 0;
    while (true)
    {
        int n = next_group();
        int arrows = n % 2 == 0 ? n / 2 : (n - 1) / 2;

        if (n % 2 == 0)
        {
            if (arrows > white || arrows > black)
                break;
        }
        else
        {
            if (arrows + 1 > white || arrows > black)
                break;

            white--;
        }

        white -= arrows;
        black -= arrows;
        groups++;

    }

    std::cout 
        << "Complete groups eliminated: " << groups 
        << "\nWhite arrows left: " << white 
        << "\nBlack arrows left: " << black 
        << std::endl;



    system("pause");
    return 0;
}