網易2018校園招聘程式設計真題之魔法币

題目

小易準備去魔法王國采購魔法神器,購買魔法神器需要使用魔法币,但是小易現在一枚魔法币都沒有,
  但是小易有兩台魔法機器可以通過投入x(x可以為0)個魔法币産生更多的魔法币。
  魔法機器1:如果投入x個魔法币,魔法機器會将其變為2x+1個魔法币
  魔法機器2:如果投入x個魔法币,魔法機器會将其變為2x+2個魔法币
  小易采購魔法神器總共需要n個魔法币,是以小易隻能通過兩台魔法機器産生恰好n個魔法币,
  小易需要你幫他設計一個投入方案使他最後恰好擁有n個魔法币。 
           

輸入描述:

輸入包括一行,包括一個正整數n(1 ≤ n ≤ 10^9),表示小易需要的魔法币數量。
           

輸出描述:

輸出一個字元串,每個字元表示該次小易選取投入的魔法機器。其中隻包含字元'1'和'2'。
           

輸入例子1:

10
           

輸出例子1:

122
           

解題思路

本題一上來看題目會使人莫名其妙，個人覺得題目有漏洞，不夠嚴謹。首先他隻要求恰好産生n個魔法币，
 其次如果不能每次都投入0個（這樣太取巧），那麼可能産生n個就會有多種選擇，
 其也沒有說明多種選擇時輸出哪種選擇。是以剛上來題目很讓人迷惑。
 開始時以為會用到動态規劃或者其他比較麻煩的算法，其實仔細看這兩個産生式你會發現，機器1産生奇數，
 機器2産生偶數。在每次都把目前所有的魔法币投入機器的前提下，這道題目就是不斷逆着求解方程罷了。
 在求解的過程中記錄機器序号。
 編完程式，運作通過，是以題目條件還是精确點好。
           

代碼塊

c++代碼：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> dst;
        while (n != )
        {
            if ((n-)>=&&(n - ) %  == )
            {
                n = (n - ) / ;
                dst.push_back();
            }
            else if ((n -  >= ) && (n - ) %  == )
            {
                n = (n - ) / ;
                dst.push_back();
            }
        }
        for (int i = dst.size() - ; i >= ; i--)
            cout << dst[i];
        cout << endl;
    }
    system("pause");
}