再帰呼び出しと完全ナビゲーション


質問です。


0から順に番号付けされるn個の要素のうち4個を選択した場合。

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

//n:전체 원소 수
//picked :지금까지 고른 원소들의 번호
//toPick : 더 고를 원소의 수
// 일때 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다

void pick(int n, vector<int>& picked, int toPick){
	//기저 사례 : 더 고를 원소가 없을때 고른 원소들을 출력한다.
    if(toPick==0){printPicked(picked); return;}
    //고를 수 있는 가장 작은 번호를 계산한다.
    int smallest = picked.empty() ? 0  : picked.back() +1;
    //이 단계에서 원소 하나를 고른다.
    for(int next = smallest; next < n; ++next){
    	picked.push_back(next);
        pick(n,picked,toPick-1);
        picked.pop_back();
    }
}

質問です。


5*5ハンドボールゲームのアルファベット単語を検索

보글 게임판에서 단어를 찾는 재귀호출 알고리즘

const int dx[8]= {-1,-1,-1,1,1,1,0,0};
const int dy[8]= {-1,0,1,-1,0,1,-1,1};

//5x5 보글 게임판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, iny x, const string& word){
	
    //기저사례 1 : 시작위치가 범위 밖이면 무조건 실패
    if(!inRange(y,x)) return false;
    
    //기저 사례 2 : 첫글자가 일치하지 않으면 실패
    if(board[y][x] != word[0]) return false;
    
    //기저 사례 3: 단어 길이가 1이면 성공
    if(word.size()==1) return true;
    
    //인접한 8칸을 검사
    for(int direction =0; direction < 8 ; ++direction){
    	int nextY = y+dy[direction], nextX = x+dx[direction];
        //다음 칸이 범위 안에 있는지 첫글자는 일치하는지 확인할 필요 없음
        if(hasWord(nextY,nextX,word.substr(1)))
        	return true;
    }
    return false;
}

이 알고리즘은 단어의 길이가 짧은 경우에만 완전탐색으로 해결할 수 있다.
단어가 긴 경우는 후에 다시 다루도록 하겠다.

質問です。


ハイキング問題

  • の各ペアの学生に対して、彼らが友達であるか否かを計算するときにペアを組むことができる方法の数.
  • 소풍 문제를 해결하는 재귀 호출 코드
    
    int n;
    bool areFriends[10][10];
    //tackenp[i]= i 번째 학생이 짝을 이미 찾았으면 true, 아니면 false
    int countPairings(bool taken[10]) {
    	//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
        int firstFree = -1;
        for(int i=0; i< n;i++){
        	if(!taken[i]){
            	firstFree = i;
                break;
            }
        }
        //기저 사례 : 모든 학생이 짝을 찾았으면 한가지 방법을 찾았으니 종료
        if(firstFree == -1) return 1;
        int ret =0;
        //이학생과 짝지을 학생을 결정한다.
        for(int pairWith = firstFree+1; pairWith < n; ++pairWith){
        	if(!taken[pairWith] && areFriends[fisrtFree][pairWith]{
            	taken[firstFree] = taken[pairWith] = true;
                ret += countPairings(taken);
                taken[firstFree] = taken[pairWith] = false;
            }
            
        }
        return ret;
    }
    
    /*
    (0,1)과 (1,0)은 같다. 같은 방법을 중복으로 세지 않도록 주의하자.
    -> 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 한다.
    -> 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일수밖에 없기에 방법이 중복될일이 없다.
    */
    
    **プログラミングコンテストで学習したアルゴリズム問題解決策(9種類のみ).