練習

d626: 小畫家真好用

https://zerojudge.tw/ShowProblem?problemid=d626

在遞迴函式中探索的方式

void 油漆桶擴散的遞迴函式(int x,int y)
{
    if( x,y座標都沒超過邊界 且 a[x][y]剛好是空格)
    {
        1. 將a[x][y]上色
        2. call 油漆桶擴散的
            遞迴函式(x,y+1);
            遞迴函式(x,y-1);
            遞迴函式(x+1,y);
            遞迴函式(x-1,y);

    }
}

Uva 11332 - Summing Digits

http://luckycat.kshs.kh.edu.tw/homework/q11332.htm

若 n = 1234567892，則：
f(n) = 1+2+3+4+5+6+7+8+9+2 = 47
f(f(n)) = 4+7 = 11
f(f(f(n))) = 1+1 = 2

因此， g(1234567892) = 2。

提示：遞迴中的每一次都拿個位數跟十位數想上的數字相加，以1234為例

123 + 4 = 127 <- 想想看怎麼取得123，怎麼取得4
12  + 7 = 19
1   + 9 = 10
1   + 0 = 1  <- 一直做到數字變成個位數，想想看怎麼判斷數字是個位數

1234如何取得123與4是種點，先想如何取得4，再想想看如何取得123，兩個再相加。

a044: 空間切割

https://zerojudge.tw/ShowProblem?problemid=a044

切割空間的影片
https://www.youtube.com/watch?v=Fjd6Oz_cgYY

1個面可以把一個空間切成2塊，以此類推，試著找出規律

1→2    2→4    3→8    4→15
5→26   6→42   7→64

如果n=4，答案是15，15是7+8，n=4的時候，4條線可以切出的區塊是11，11是7+4，觀察查看看其中的關係。

d619: 奇摩知識

https://zerojudge.tw/ShowProblem?problemid=d619

要先知道什麼是二進位，例如9可以轉成1001

題目的意思就是假如當你輸入4的時候，1~4這些數字都要被轉成2進位

1 → 1
2 → 10
3 → 11
4 → 100

把這些轉出來的二進位數字的1加總，就會得出5，而5就是我們要的答案

第一步就是試著用遞迴將10進位轉成2進位，試著寫出int convertToBinary(int n)這樣的function來計算n轉成2進位後總共有幾個1，convertToBinary(3)結果是2。

假如說數字是7，2進位就是111，取出11(1)最右邊的1，再將111變成11，也就是3，如何將7變成3，其實就是7/2。

解答區

d626: 小畫家真好用

#include <bits/stdc++.h>
using namespace std;
int n=0;
char a[101][101];

void dfs(int x,int y)
{
    //此格子在地圖的範圍內，而且還沒有被上色
    if(x>=0&&y>=0&&x<=n&&y<=n&&a[x][y]=='-')
    {
        a[x][y]='+'; //上色
        dfs(x,y+1);  //往下方探索 ↓
        dfs(x,y-1);  //往上方探索 ↑
        dfs(x+1,y);  //往右方探索 →
        dfs(x-1,y);  //往左方探索 ←

    }
}

int main()
{

    int x,y;

    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];//輸入圖畫

    cin>>x>>y; //輸入倒油漆的位置

    dfs(x,y);//開始用油漆桶上色

    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<a[i][j];//輸出已經塗色的圖畫
        }
        cout<<endl;
    }

    return 0;

}

a044: 空間切割

#include<iostream>
using namespace std;

int extraCut(int n)
{
    if(n==1){
        return 2;
    }else{
        return extraCut(n-1)+n;
    }
}

int cut(int n)
{
    if(n==1){
        return 2;
    }
    else{
        return cut(n-1)+extraCut(n-1);
    }
}

int main(void)
{
    int n;
    while(cin>>n){
        cout << cut(n) << endl ;
    }
    return 0;
}

另外補充，這個其實是有公式的

$$ 1+\frac{(n)(n^2+5)}{6} $$

想了解的同學可以參考這個

Uva 11332 - Summing Digits

#include <iostream>
using namespace std;
int f(int a)
{
    int sum=0;
    while(a!=0)
    {
        sum+=a%10;
        a/=10;
    }
    return sum;
}
int main()
{
    int x;
    while(cin>>x)
    {
        if(x==0){break;}
        while(f(x)>=10) { x=f(x); }
        cout<<f(x)<<endl;
    }

    return 0;
}

d619: 奇摩知識

要先知道什麼是二進位，例如9可以轉成1001

題目的意思就是假如當你輸入4的時候，1~4這些數字都要被轉成2進位

1 → 1
2 → 10
3 → 11
4 → 100

把這些轉出來的二進位數字的1加總，就會得出5，而5就是我們要的答案

第一步就是試著用遞迴將10進位轉成2進位

#include <iostream>
using namespace std;

int convertToBinary(int n)
{
  if (n / 2 != 0) {
    return n % 2 + convertToBinary(n / 2);
  }
    else{
        return 1;
    }
}


int main()
{

  int n, sum = 0;
  cin >> n;

  for (int i = 1; i <= n ; i++){
    sum += convertToBinary(i);
  }

  cout<<sum;

}

AC版

上面的方法是最直覺的，但是在zerojudge會TLE
這邊提供一個可以AC的方法

先備知識

1. 如何知道一個數是不是2的次方：n&(n-1)
   這個叫做bitwise and，參考資料如
   https://www.programiz.com/c-programming/bitwise-operators#and
   如果結果是0，表示他是二的次方

2. 如何知道一個數是２的幾次方：log(n)/log(2)

3. 找出答案的規律

程式

#include<iostream>
#include <cmath>
using namespace std;

int table[33]={1};

void init(){
    for(int i=1;i<33;i++){
        table[i]=int(2*table[i-1]+pow(2,i-1)-1);
    }
}


int getBinSum(int n){
    if(n==1) return 1;
    else{
        if( !(n&(n-1)) ){
            return table[int(log(n)/log(2))];
        }else{
            int tmp=n;
            do{tmp--;}while( (tmp&(tmp-1)) );
            return table[int(log(n)/log(2))]+getBinSum(n-tmp)+n-tmp;
        }
    }
}

int main(){
    int n;
    init();
    while(cin>>n){
        cout<<getBinSum(n)%1000000000<<endl;
    }
}