iT邦幫忙

1

【c/c++學習筆記】解題記錄CodeWar-Row of the odd triangle

本文適合對象: 對c/c++有初步認識者、初學練習者
題目來源: CodeWar-Row of the odd triangle
撰文動機: 近來在學習c++,以codewar的題目自我練習,也可將做題碰到的問題記錄下來分享

題目: 有一個數字三角形的排列如下:

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29

寫一個函數可以讀入整數n,並將第n行的數字以vector的形式輸出,
譬如
odd_row(1) == [1]
odd_row(2) == [3, 5]
odd_row(3) == [7, 9, 11]
(程式必須可以處理大整數)

解題思路:
本題會用到幾個概念: 國中數學、vector的概念、型別轉換。

數學的部分不是太難,
可以看到第n行恰恰有n個數字,
每個數字之間相差2
只要能算出第n行的開頭數字,
便能簡單的將每個數字算出來。

小馬的做法是計算第n行前面有幾個數,
n-1行共有1+2+3+…+(n-1)=n*(n-1)/2個數字,
因此第n行的開頭數字便是1+n*(n-1)

再來便是宣告一個vector,
用for迴圈添加元素,
不過這看似簡單的程式,
對新手來說卻意外的容易出錯,
第一支嘗試解答的程式如下:

#include <vector>

std::vector<unsigned long long> odd_row(unsigned int n) {
    vector<unsigned long long> nums;
    for(unsigned int i=0;i<n;i++){
        nums.push_back(1+n*(n-1)+2*i);
    }
    return nums;
}

你能看出上述程式錯在哪裡嗎?
vector來自命名空間std,必須寫std::vector
而非單純寫vector(不然前面就要加一行using std::vector;)

第二個錯誤相當不容易看出來,
因為n的型別是unsigned int
單純計算1+n*(n-1)+2*i的型別應該也是unsigned int
可以在n前面加上括號(unsigned long long)n轉型為unsigned long long

完整解答程式如下:

#include <vector>

std::vector<unsigned long long> odd_row(unsigned int n) {
    std::vector<unsigned long long> nums;
    for(unsigned int i=0;i<n;i++){
        unsigned long long num=1+(unsigned long long)n*(n-1)+2*i;
        nums.push_back(num);
    }
    return nums;
}

尚未有邦友留言

立即登入留言