0 x 0 B鋼-再帰

9781 ワード
テキストリンク
アルゴリズムの説明
再帰:1つの関数で自分でタスクを実行するアルゴリズムを再呼び出します.
プロセス思考を捨て,数学的帰納法を用いて問題を解決しなければならない.
-再帰関数の条件
一部の入力では、自分を呼び出さずに終了する必要があります(Base condition)
すべての入力はbase条件に収束する必要があります
-復帰に関する情報1
関数のパラメータが何であるか,どの程度計算されているかを明確に決定し,自分に渡す必要がある.
すべての再帰関数は、重複文のみを使用して同じ操作を行う関数を作成できます.
再帰コードは、繰り返し文よりも簡潔ですが、メモリ/時間の損失が発生します.
-復帰に関する情報2
1つの関数が複数回呼び出されると、効率が低下する可能性があります.
ex)フィボナッチ関数を簡単に実装すると,自分自身をどんどん呼び出してしまうため,非常に大きな時間的複雑度O(1.1618^N)が生じる.
-復帰に関する情報3
再帰関数が自分を呼び出すと、スタック領域に蓄積されます.
スタックメモリが限られている場合、実行時にエラーが発生します.返された回数が10000回を超えても
練習問題1-繰り返し平方
a^B mod m
using ll = long long;
ll func1(11 a, ll b,ll m) {
	ll val  = 1;
    while(b--) val = val * a %m;
    return val;
    }
ロングデータ型によるオーバーフロー防止
aを掛けるたびに、オーバーフローを防ぐために、私たちはm->に分けます.私たちは残りを求めたいからです.
21233232334の1の位置を探していると、すべての桁数を計算するのではなく、1を乗じた位置になるという理屈は10に変えただけです.
1629 . 乗算＃ジョウサン＃
a^N * a^N = a^2N
12 ^ 58 = 4(mod 67) -> 12 ^ 116 = 16(mod 67)
1勝を計算できる.
K勝を計算すれば2 k勝と2 k+1勝もO(1)に計算できる.
#include <bits/stdc++.h>
using namespace std;
#define ll long long


ll a, b, c;
ll func(ll a, ll b)
{
	if (b == 0)
		return 1;
	if (b == 1)
		return a %c;
    //종료 조건을 설정
	if (b % 2 == 1)
		return func(a, b - 1) * a;
    // b가 홀수일경우 b-1을 해주고 a를 한번곱해줘서 b를짝수로만들어줌
	ll half = func(a, b / 2) % c;
    // K승을 구해서 곱해주면 2K승을 구할수있다
	return half * half % c;
	

}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> a >> b >> c;

	cout << func(a, b) % c << '\n';
    //함수를 호출해줌 결과값이 c보다 클수있기 때문에 %c
}
11729 . ハノイタワー
  • 関数を定義する
    • void func(int a, int b, int n)
    nブロックの円板をa番柱からb番柱に移動する方法の関数を出力します.
  • base condition
    • n=1の場合cout<戻り式n−1枚の円板を柱aから柱6−a−b,func(a,6−a−b,n−1)に移動する.
    n号円板は柱aから柱bに移動する
    n−1枚の円板を柱6−a−bから柱b上にfunc(6−a−n,b,n−1)移動させる.
    #include <bits/stdc++.h>
using namespace std;
    コードを入力してください
    void func(int a, int b, int n)
{
	if (n == 1)
	{
		cout << a << ' ' << b << '\n';
		return;
	}
	func(a, 6 - a - b, n - 1);
	cout << a << ' ' << b << '\n';
	func(6 - a - b, b, n - 1);

}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int k;
	cin >> k;

	cout << (1 << k) - 1 << '\n';
	func(1, 3, k);
}
    プログラム指向の思考から抜け出し、数学的な接近をしてこそ、問題を理解することができる.
    1枚の板の時だけ問題を解決することができます.
    k個の時k+1個の時に問題を解決できることを考え方として問題を解決しなければならない.
    解説から見て問題はよく理解されていないが.
    https://www.youtube.com/watch?v=AogMbfRwguk
    一度見て、問題を再理解して、もっと理解したようです.
  • z 
    • #include <bits/stdc++.h>
using namespace std;


int func(int n,int r,int c)
{
	if (n == 0)
		return 0;
	int half = 1 << (n - 1);

	if (r < half && c < half) return func(n - 1, r, c);
	if (r < half && c >= half) return half * half + func(n - 1, r, c - half);
	if (r >= half && c < half) return 2 * half * half + func(n - 1, r - half, c);
	return 3 * half * half + func(n - 1, r - half, c - half);
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n,r,c;
	cin >> n >> r >> c;

	cout << func(n,r,c) << '\n';
	
}
    その格子の番号は私が通った格子の番号と同じで、これは問題を解決するための考えです.
    矩形を4等分すると、各矩形の1辺は現在2^n-1であり、それを乗じて矩形内の数字であり、1、2、3、4の矩形ごとにそれを加えればよい.
    これにより,nが0になる前に,その格を超える数字を加えることで,その格の番号を知ることができる.
    17478 . 貴関数は何ですか.
    #include <bits/stdc++.h>
using namespace std;

int n;
void func(int cnt)
{
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "\"재귀함수가 뭔가요?\"" << '\n';
	if (cnt == n)
	{
		for (int i = 0; i < cnt; i++)
		{
			cout << "____";
		}
		cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"" << '\n';
		for (int i = 0; i < cnt; i++)
		{
			cout << "____";
		}
		cout << "라고 답변하였지." << '\n';
		return;
	}
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어." << '\n';
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지." << '\n';
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"" << '\n';
	func(cnt + 1);
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "라고 답변하였지." << '\n';




}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << '\n';
	func(0);
}
    これは、数値と数値の再帰を入力することで文字列を出力する問題です.
    私はまず数字nをグローバルに宣言し、入力を受け入れた.
    0からnまでの再帰関数を呼び出すことで問題を解決した.(パラメータcntを0から開始することにより、nをベース条件とする)
    まず最初の日に1つ~の部分を印刷します.
    func(0)を呼び出します.
    すべての文字列の前に、現在のcntのサイズが出力されます.
    次の再帰関数は何を呼び出し、baseconditionで最後の文字列を出力し、returnで終了します.
    「文字列の先頭と末尾ではなく、で表すべき特殊文字です.
    1780 . 紙の数
    #include <bits/stdc++.h>
using namespace std;

int n;

int board[2200][2200];

int arr[3];

void func(int n,int x,int y)
{
	if (n == 0)
		return;

	int number = board[x][y];
	for (int i = x; i < x+n; i++)
	{
		for (int j = y; j < y+n; j++)
		{
			if (number != board[i][j])
			{
				for (int nx = 0; nx < 3; nx++)
				{
					for (int ny = 0; ny < 3; ny++)
					{
						func(n / 3, x + (nx* n/3), y +(ny * n / 3));

					}
				}
				return;
			}
		}
	}

	arr[number + 1]++;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
		}
	}

	func(n,0,0);

	for (int ans : arr)
	{
		cout << ans << '\n';
	}
	
}
    配列のサイズnを入力し、配列を入力して埋めます.正解はarr配列に-1、0、1の数を加えます.
    func関数は、n行列の1つの辺長、x行の開始座標、y列の開始座標をパラメータとして受け入れる.
    nは0日を基本条件としていますが、nを3で割って1にすると、どうせセルの大きさは1で、それぞれのセルの大きさが同じ配列になっているので、エラーがなければ0にはなりません.
    次のboard[x][y]を基準にx+n、y+nでナビゲートし、重複文を終了するとそのセルは同じ値になるのでarr配列に値を上げます(-1から1を配列のインデックスとして加算します)
    中間に異なる値が現れると、矩形を9つ、すなわちn/3に分け、9つの矩形ごとのx、y座標を加えてfuncを呼び出す.
    関数が終了するとarrの値が出力されます.
    1992 . 四叉木
    #include <bits/stdc++.h>
using namespace std;

int n;

int board[65][65];


void func(int n,int x,int y)
{
	if (n == 0)
		return;

	int number = board[x][y];
	for (int i = x; i < x+n; i++)
	{
		for (int j = y; j < y+n; j++)
		{
			if (number != board[i][j])
			{
				cout << '(';
				func(n / 2, x, y);
				func(n / 2, x, y + (n / 2));
				func(n / 2, x + (n/2), y);
				func(n / 2, x + (n / 2), y + (n / 2));
				cout << ')';
				return;
			}
		}
	}

	cout << number;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.size(); j++)
		{
			board[i][j] = str[j] - '0';
		}
	}

	func(n, 0, 0);
}
    従来の問題と解決策は同じであったが、出力値の部分で重複文を終了するとnumberが出力され、途中で異なる値()が発生し、funcが呼び出される前と後に出力されると、各圧縮値が出力される.
    2447 . 星を撮る-10
    #include <iostream>
using namespace std;
void star(int i, int j, int num)
{
    if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
        cout << ' ';
    }
    else
    {
        if (num / 3 == 0)
            cout << '*';
        else
            star(i, j, num / 3);
    }
}
int main() {
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < num; j++)
            star(i, j, num);
        cout << '\n';
    }
}
    分割征服で星を撮影する問題です.
    numを入力すると、各セルのマルチスター関数のみが呼び出され、この関数からスペースまたは星が出力されます.

    まず、例の最も基本的な長方形のスペースの座標は、1、1、1、4、1、7です.
    4,1 4,4 4,7 ...
    すなわち,i%3=1&&j%3=1というルールが見つかる.
    次が9個の矩形集合の場合、中央の空座標は3、3、3、4、5、4、4、4、5…
    すなわち、ルール(i/3)%3=1&(j/3)%3=1を見つけることができます.
    これらの規則をnum/3に再帰的に分け,スペースか星かを区別して解くことができる.
    2448 . 星をたたく
    #include<cstdio>
 
char DB[][6]=
{ "  *  ",
  " * * ",
  "*****" };
char MAP[3500][6500];
 
void solve(int n, int y, int x)
{
    if (n == 1)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 5; j++)
                MAP[y + i][x + j] = DB[i][j];
        return;
    }
    solve(n / 2, y, x + 3 * n / 2);
    solve(n / 2, y + 3 * n / 2, x);
    solve(n / 2, y + 3 * n / 2, x + 3 * n);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    solve(n / 3, 0, 0);
    for(int i=0;i<n;i++,puts(""))
        for(int j=0;j<2*n-1;j++)
            printf("%c", MAP[i][j] == '*' ? '*' : ' ');
    return 0;
}
    上記のように,星を撮影する場所のルールを探し出し,分割によって出力を征服する.
    今はまだよく分からないので、まずグーグルで問題を解決してから、スキルを増やせば、よく勉強しなければなりません.
    単純なフル・スタンバイ・データベースのスクリプトとシステム・データベースのバックアップが必要かどうか
    [DQL]結合