← 返回题目列表

AtCoder · APG4b_v

V. 2.05.递归函数

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_v 任务ID:3768

上一页 | 下一页

## 注释 递归示例(一些)→ 如何设计递归函数→ 递归函数的模式和练习→ Stack Overflow 递归实际操作的图像(显示它如何扩展为范围)→ 如何设计递归函数(强调不考虑图像) 去0的例子、中途输出的例子、去n的例子、使用数组的例子、n和m同时减少的例子 作为递归的例子,哪个更好:“求和”或“输出 n 次”?还有更好的吗? 我应该发布与 for 的比较吗? 我实在不喜欢这种写作方式。但是,如果你突然使用`sum`函数,可能会引起混乱>接下来,假设你已经完成了计算从`0`到`n-1`的总和的函数`sum_p`。 解释复杂吗? >定义了多个变量“n”和“s”,但就像范围一章中解释的规则一样,假设内部变量优先。 最好用幻灯片什么的来解释一下操作。 我正在将其写入类似堆栈的图像中,但在这种情况下,删除未执行的行似乎是一个坏主意。 我感觉我要生气了。 (既然和数学归纳法很像,那是不是公理大于保证?) > 这种写法的正确运行是由**数学归纳法**保证的,高中数学都有涉及。 - 可以将其称为“基本情况”和“递归步骤”吗? - 使用 if 语句提前返回终止条件还是使用 `if (termination condition) { /* base case */ } else { /* recursive step */ }` 更好? - 我觉得最好将其与其他分开,以便更容易直接看到“基本情况”和“递归步骤”。 - 我应该画一个状态转换的图像吗?

要点

  • “在函数内调用相同的函数”递归调用这就是所谓的
  • 执行递归的函数再帰関数这就是所谓的
  • 无需递归调用即可完成的处理基本情况这就是所谓的
  • 进行递归调用并使用结果的过程。递归步骤这就是所谓的
  • 实现递归函数的3个步骤
  • 1.决定“参数”、“返回值”和“处理内容”
  • 2.递归步骤的实现
  • 3. 基本案例实现

再帰関数

要理解递归函数,您需要理解函数。 如果您对 1.15.関数有模糊的记忆,请回顾一下。

递归函数比较难,所以如果看完解释还是不明白,可以直接继续。

到目前为止,我们一直使用循环结构(例如 for 循环和 while 循环)作为执行重复处理的方式。
再帰也是一种重复处理的方法。

递归是“在另一个函数中调用相同的函数”。另外,这样的函数是 它被称为再帰関数。

递归是比循环语法更强大的迭代方法,可以简洁地执行使用循环语法难以编写的处理。
乍一看似乎很难理解,但它是一个强大的方法,所以学习如何使用它。

作为示例,请考虑“计算 0 到 n 之和的函数”。

这可以使用我们到目前为止一直使用的 for 循环和 while 循环来编写,但是如果您使用递归函数来编写它,它将如下所示。

#include <bits/stdc++.h>
using namespace std;

int sum(int n) {
  if (n == 0) {
    return 0;
  }

  // sum関数の中でsum関数を呼び出している
  int s = sum(n - 1);
  return s + n;
}

int main() {
  cout << sum(2) << endl;    // 0 + 1 + 2 = 3
  cout << sum(3) << endl;    // 0 + 1 + 2 + 3 = 6
  cout << sum(10) << endl;   // 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
}
実行結果
3
6
55

sum 函数在 sum 函数内调用。像这样的函数调用递归调用。

递归函数的行为

下一张幻灯片使用上面的 sum 函数。 这解释了调用sum(3)时的行为。

由于递归函数具有相同的函数名称,因此可能感觉它们在调用自身,并且它们的行为可能看起来令人困惑。
在这种情况下,您可以考虑“使用不同的参数调用不同的函数”。

在上面的例子中 让我们写出调用sum(3)时的行为。

  • sum(3)所以 调用sum(2)并将结果加 3 并返回。 调用
  • sum(2)所以 调用sum(1)并将结果加 2 并返回。
  • sum(1)所以 调用sum(0)并将结果加 1 并返回。
  • sum(0)返回 0。

这里,它被称为 如果我们将sum(3), sum(2), sum(1), sum(0)分割成单独的函数并考虑它们,我们会得到以下结果。

#include <bits/stdc++.h>
using namespace std;

// 0~0の総和を求める
int sum0() {
  return 0;
}
// 0~1の総和を求める
int sum1() {
  int s = sum0();
  return s + 1;  // (0~0の総和) + 1 = 1
}
// 0~2の総和を求める
int sum2() {
  int s = sum1();
  return s + 2;  // (0~1の総和) + 2 = 3
}
// 0~3の総和を求める
int sum3() {
  int s = sum2();
  return s + 3;  // (0~2の総和) + 3 = 6
}

int main() {
  cout << sum3() << endl;  // 6
}
実行結果
6

sum1, sum2, sum3有类似的处理,但是 仅sum0的处理方式不同。 由于重复处理可以用 while 和 for 语句来概括, 这种重复调用可以与递归调用归为一组。

我们再看一下原来的递归函数。

#include <bits/stdc++.h>
using namespace std;

// 0 ~ nの総和を求める
int sum(int n) {
  if (n == 0) {
    // sum0のケースを場合分け
    return 0;
  }

  // それ以外のケース
  int s = sum(n - 1);  // 1~(n-1)の総和を計算
  return s + n;  // nを足して返す
}

int main() {
  cout << sum(3) << endl;  // 6
}
実行結果
6

递归函数可以正常工作,因为递归调用链有一个终点。 在这个例子中 第一次调用n时的值减1,到0时通过if语句进行分支,不再发生递归调用。 它工作正常,因为调用链结束了。


递归函数的属性

在介绍实现方法之前,我们先总结一下递归函数的性质。

递归函数的内容大致可以分为以下两类处理。

  • 基本情况:无需递归调用即可完成的处理
  • 递归步骤:通过递归调用并使用结果执行的处理

在 sum 函数示例中,基本情况和递归步骤如下。

// n を受け取って、0~n の総和を計算して返す関数
int sum(int n) {
  // ベースケース
  if (n == 0) {
    return 0;
  }

  // 再帰ステップ
  int s = sum(n - 1);
  return s + n;
}

此外,递归函数要正确工作还必须满足以下条件。

  • 递归调用链已结束

换句话说,“在递归步骤中重复递归调用时,始终会达到基本情况。”

如果不满足此条件,则会发生无限循环。

如何实现递归函数

一开始我不太明白递归函数可以进行什么样的处理, 可能很难掌握,但是当您遵循递归函数的实现并实际执行它们时,您就会理解。

这里我们将解释如何尽可能仔细地实现递归函数。

1.决定“参数”、“返回值”和“处理内容”

函数接收处理所需的变量作为参数,在函数内执行处理并返回结果。 您需要决定“参数”、“返回值”和“处理内容”。

“处理内容”意味着计算“返回值”,它们通常意味着同一件事。

求和函数示例

引数 int n (大于或等于0的整数)
返回值 0 \sim n之和 计算
処理内容 0 \sim n的总和

函数的一般形状在此确定。这是求和函数的示例:

// 0 ~ n の総和を返す
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する
}

2.递归步骤的实现

接下来我们考虑一下可以用什么样的递归调用来完成这个过程,也就是递归步骤的内容。

我们考虑一下是否可以利用“不同参数的递归调用结果”来实现“处理内容”。 这取决于您想要实施的流程,因此在您习惯之前可能会很困难。

求和函数示例

「0 \sim n的总和是0 \sim (n-1)的总和 可以通过添加n来计算。 这里“0 \sim (n-1)的总和是 通过递归调用sum(n - 1)获得。

// 0 ~ n の総和を返す
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する

  // 再帰ステップ
  int s = sum(n - 1);  // 0 ~ (n-1) の総和
  return s + n;  // 0 ~ n の総和
}

3. Base case实现(无需递归调用即可完成的处理)

首先,考虑什么是基本情况,即什么时候可以在不进行递归调用的情况下完成。

接下来,使用if语句分离基本情况并实现处理。

让我们确保在给定适当的参数时,递归步骤中的递归调用最终将到达基本情况。如果您无法达到您刚刚想到的基本情况,则递归步骤或基本情况是错误的。我们再想一想。

请注意,可能有多个基本情况。

求和函数示例

求和函数是“ 由于它是计算0 \sim n之和的函数, 对于n == 0,您可以立即看到结果为0。因此,这种情况对应于基本情况。

另外,2中实现的递归步骤中的递归调用sum(n - 1)终于 由于我们到达了情况n == 0,我们知道我们总是到达基本情况。

// n を受け取って、0~n の総和を計算して返す関数
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する

  // ベースケース
  if (n == 0) {
    return 0;  // 再帰呼び出しをせずとも 0 という結果が確定している
  }

  // 再帰ステップ
  int s = sum(n - 1);  // 0 ~ (n-1) の総和
  return s + n;  // 0 ~ n の総和
}

现在是递归函数sum已完成。

让我们再次总结一下如何编写递归函数。

  1. 决定“参数”、“返回值”、“处理内容”
  2. 实现递归步骤
  3. 基本案例实施

实现递归函数一开始可能看起来很困难。 然而,当您多次阅读和编写递归函数时,总有一天它会直观地变得有意义。

此外,虽然我通过考虑递归步骤然后考虑基本情况来解释该过程, 首先考虑递归步骤并不总是一个好主意。 在某些情况下,首先考虑基本情况可能更容易,或者您可以在考虑递归步骤中使用的关系表达式时想出基本情况。 只要满足“递归调用链有终点”这个条件就可以了,所以请随意用自己的想法来写。


递归函数的实现示例

我们将介绍一些递归函数的模式。 虽然有些东西可以使用 for 语句或 while 语句写得更简洁,但这是递归函数的示例。

计算从A到B的总和的函数:sum_range

点击打开

两个整数a和b (a ≤ b), 计算a, a+1, …, b - 1, b之和的函数 使用递归函数实现sum_range。

举一个具体的例子,sum_range(3, 7)返回 25,因为 3+4+5+6+7=25。

1.决定“参数”、“返回值”、“处理内容”

項目 内容
引数 int a, int b
返回值 a ∼ b之和 (int型)
処理内容 a ∼ b的总和

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
}

2.递归步骤的实现

「a ∼ b” 之和 = “a ∼ (b - 1)总和'+ 关系式 b成立。

「a ∼ (b - 1)的总和是参数 将b减少 1 由于它对应的是递归调用sum_range的结果,所以这个关系表达式的实现就是递归步骤。

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

3. 基本案例实现

考虑无需递归调用即可确定结果的情况。

a == b当“a ∼ b” 之和 = “a ∼ a” 之和 = “a”,因此这种情况成为基本情况。

另外,在 2 中实现的递归步骤中,a没有改变b减 1,导致一系列递归调用。 根据关系a ≤ b,b终于 由于它等于a,我们知道递归调用结束。

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

现在sum_range已完成。

#include <bits/stdc++.h>
using namespace std;

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

int main() {
  cout << sum_range(0, 4) << endl; // 0 + 1 + 2 + 3 + 4 = 10
  cout << sum_range(5, 8) << endl; // 5 + 6 + 7 + 8 = 26
}

実行結果

10
26

在此实现示例中, 关注关系表达式a ∼ b” 之和 = “a ∼ (b - 1)总和'+ 关系式 b, 我通过减少sum_range(a, b - 1) + b和b的策略来实现它,但是 关系式a ∼ b” 之和 = “(a + 1) ∼ b总和'+ 关系式 a也成立,所以sum_range(a + 1, b) + a和a来实现。

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return a + sum_range(a + 1, b);  //「a~bの総和」= a +「(a+1)~bの総和」
}

数组元素总和:array_sum

点击打开 实现函数“array_sum”,该函数计算作为参数(引用)给出的“int”类型数组的所有元素的总和。

1.决定“参数”、“返回值”、“处理内容”

由于这是一个计算数组总和的函数,因此参数通过引用接收数组。 (实际上,这不能作为递归函数成功实现,但我会在检查步骤2后更正它。)
項目 内容
引数 vector<int> &data
返回值 data的元素之和 (int型)
処理内容 data的元素总和

// dataの要素の総和を計算する
int array_sum(vector<int> &data) {
}

2.递归步骤的实现

可以看出以下关系成立。
「配列の要素の総和」=「配列の先頭の要素」+「配列の2番目以降の要素の総和」
然而,事实上,使用递归调用无法成功计算。 该关系表达式可以稍微改写如下。
「1番目以降の要素の総和」=「1番目の要素」+「2番目以降の要素の総和」
此外,以下关系也成立。
「2番目以降の要素の総和」=「2番目の要素」+「3番目以降の要素の総和」
「3番目以降の要素の総和」=「3番目の要素」+「4番目以降の要素の総和」
...
这些是变量 通过使用i,我们可以总结如下。 “
「i番目以降の要素の総和」=「i番目の要素」+「i+1番目以降の要素の総和」
「i+1之后的元素之和”部分可以通过递归调用得到。 第 1 步中确定的参数还不够,现在我们需要将变量 i 添加到参数中。让我们回到步骤 1 并修复它。

1.决定“参数”、“返回值”、“处理内容”(重做)

将 `int i` 添加到参数中 事实证明,通过使其成为计算i之后元素之和的函数,可以将其实现为递归函数。 该函数的“参数”、“返回值”和“处理细节”如下。 第
項目 内容
引数 vector<int> &data, int i
返回值 data的 可以考虑i之后的元素之和 (int型)
処理内容 data的 可以考虑i之后的元素总和

该函数的函数名称是“array_sum_from_i”。 那么,函数 sum_array 的“计算给定数组所有元素之和”的最初目的可以通过使用 0 调用 array_sum_from_i 的参数 i 来实现。 当一个功能是通过添加另一个功能来实现时,称为辅助功能。 在此示例中,为实现“array_sum”而添加的“array_sum_from_i”是一个辅助函数。
// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
}

// dataの全ての要素の総和を計算する
int array_sum(vector<int> &data) {
  return array_sum_from_i(data, 0);
}
从现在开始,我们将看看 `array_sum_from_i` 的实现。

2.递归步骤的实现(re)

到目前为止,i第 th" = " 之后的元素之和i第一个元素“+” 可知关系式“i+1之后的元素之和”成立。 ” 通过递归调用 array_sum_from_i(data, i + 1) 可以求出i+1之后的元素之和。 由于是
// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

3. 基本案例实现

「i之后的元素之和,所以我们知道当没有更多目标元素时,即当`i == data.size()`时,答案为0。因此,该案例成为基本案例。 在递归步骤中,参数 i 加 1,并发生一系列递归调用,因此最终应该满足 i == data.size() 。 从这里我们可以看出,递归链已经结束了。
// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    return 0;  // 対象の要素がないので総和は0
  }
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

`array_sum_from_i` 现已完成。 包括“array_sum”在内的整个程序如下所示:
#include <bits/stdc++.h>
using namespace std;

// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    return 0;  // 対象の要素がないので総和は0
  }
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

// dataの全ての要素の総和を計算する
int array_sum(vector<int> &data) {
  return array_sum_from_i(data, 0);
}

int main() {
  vector<int> a = {0, 3, 9, 1, 5};
  cout << array_sum(a) << endl;   // 0 + 3 + 9 + 1 + 5 = 18
}

実行結果

18

函数 is_prime 判断 N 是否为素数

点击打开 正整数 实现函数 `is_prime` 来确定N是否是素数。 仅使用 N作为参数, 使用递归函数很难实现判断N是否为素数的过程,因此我们引入一个像array_sum这样的辅助函数。 ” 范围i \sim N - 1将辅助函数“has_divisor”实现为递归函数,用于确定N的除数是否存在。 当 N为3或更大时,“ “N是素数”的条件是“2 \sim N-1将辅助函数“has_divisor”实现为递归函数,用于确定N没有约数,”并且由于 1 不是质数而 2 是, ” 判断N是否为素数的函数“is_prime”可以使用“has_divisor”来实现。 检查是否存在

1.决定“参数”、“返回值”和“处理内容”

項目 内容
引数 int N (N ≥ 3), int i
返回值 i ∼ N - 1将辅助函数“has_divisor”实现为递归函数,用于确定N的约数 返回为bool类型 判断
処理内容 i ∼ N - 1将辅助函数“has_divisor”实现为递归函数,用于确定N的约数是否存在

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
}

2. 递归步骤的实现 / 3. 基本案例的实现

首先, 如果i是N的约数,则判定为真。 在其他情况下,' 结果是“i + 1 \sim N - 1将辅助函数“has_divisor”实现为递归函数,用于确定N有除数吗?” ” “i + 1 \sim N - 1将辅助函数“has_divisor”实现为递归函数,用于确定N有除数吗?”是通过递归调用获得的。 i是 它可能以N这是基本情况,因为目标整数不存在并且被确定为假。 另外, 如果它是i是 它可能以N的除数,那么它肯定是真的,所以这也是基本情况之一。 所以实现看起来像这样:
// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
  // ベースケース1
  if (i == N) {
    // そもそも対象となる整数が無いのでfalse
    return false;
  }
  // ベースケース2
  if (N % i == 0) {
    // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する
    return true;
  }

  // 再帰ステップ
  // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる
  // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい)
  return has_divisor(N, i + 1);
}

现在我们已经实现了`has_divisor`。您现在所要做的就是使用它来实现“is_prime”。
#include <bits/stdc++.h>
using namespace std;

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
  // ベースケース1
  if (i == N) {
    return false;
  }
  // ベースケース2
  if (N % i == 0) {
    // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する
    return true;
  }

  // 再帰ステップ
  // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる
  // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい)
  return has_divisor(N, i + 1);
}

bool is_prime(int N) {
  if (N == 1) {
    // 1は素数ではない
    return false;
  }
  else if (N == 2) {
    // 2は素数
    return true;
  }
  else {
    // 2~(N-1)の範囲に約数が無ければ、Nは素数
    return !has_divisor(N, 2);
  }
}

int main() {
  cout << is_prime(1) << endl;  // 0
  cout << is_prime(2) << endl;  // 1
  cout << is_prime(12) << endl; // 0
  cout << is_prime(13) << endl; // 1
  cout << is_prime(57) << endl; // 0
}

実行結果

0
1
0
1
0
请注意,这里介绍的素性测试函数并不实用,因为有更有效的方法来测试素性。

数组操作reverse_array

点击打开 此示例仅显示示例实现。 请自行遵循该程序或尝试自行运行。 以下程序是函数“reverse_array”的实现示例,该函数返回按相反顺序重新排列引用给出的数组的结果。
#include <bits/stdc++.h>
using namespace std;

// dataのi番目以降の要素を逆順にした配列を返す
vector<int> reverse_array_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    vector<int> empty_array(0);  // 要素数0の配列
    return empty_array;
  }

  // 再帰ステップ
  vector<int> tmp = reverse_array_from_i(data, i + 1);  // dataのi+1番目以降の要素を逆順にした配列を得る
  tmp.push_back(data.at(i));  // 末尾にdataのi番目の要素を追加
  return tmp;
}

// 配列を逆順にしたものを返す
vector<int> reverse_array(vector<int> &data) {
  return reverse_array_from_i(data, 0);
}

int main() {
  vector<int> a = {1, 2, 3, 4, 5};
  vector<int> b = reverse_array(a);
  for (int i = 0; i < b.size(); i++) {
    cout << b.at(i) << endl;
  }
}

実行結果

5
4
3
2
1

# 表达式计算示例 给定一个由非负整数、加法/乘法和括号组成的表达式<var>E</var>,请输出计算<var>E</var>的结果。 ## 定义公式和计算 定义公式<var>E</var>的计算结果如下表所示。 |<var>E</var>|计算结果| |--|--------| |`(` 公式 1 `+` 公式 2 `)`|**公式 1 和公式 2 的计算结果之和**| |`(` 公式 1 `*` 公式 2 `)`|**公式 1 的计算结果与公式 2 的计算结果的乘积**| |1 位整数 (`0`,`1`,`2`,`3`,`4`,`5`,`6`,`7`,`8`,`9`)|十进制表示的整数| 表达示例 - `(1+2)` - `((1+2)*(3+4))` -`5` 这些计算的结果如下。 - 3 - 21 - 5 不是表达式的示例 - `1+2` - `(1+2)(3+4)` - `(5)` ## 程序模板 请使用下面的模板来实施。 <pre class="prettyprint linenums source-code">#include <bits/stdc++.h>; 使用命名空间 std; // stoi(s) ...将字符串 s 转换为整数 // 从以下形式的表达式中提取表达式1、运算符、表达式2 (表达式1 运算符表达式2) void extract(字符串 e, 字符串 &amp;exp1, char &amp;op, 字符串 &amp;exp2) { int 嵌套 = 0; // 表达式嵌套级别 整数 i = 1; // 从'('之后开始读取 // 查找运算符 for (; i < e.size(); i++) { if (e.at(i) == '(') 嵌套++; if (e.at(i) == ')') 嵌套 --; if ((e.at(i) == '+' || e.at(i) == '*') &amp;&amp; 嵌套 == 0) { op = e.at(i); 打破; } } // s.substr(i, len) ...从 s 的第 i 个字符返回 len 个字符 exp1 = e.substr(1, i); exp2 = e.substr(i+1, e.size()-i); } int calc_expression(字符串 e) { //(在这里实现) } int main() { 字符串 E; 辛>> E; 计算<<计算表达式(E) <<结束; } </前> `extract` 的用法如下。 <pre class="prettyprint source-code">字符串 exp1, exp2; 字符操作; 提取(“(1+(2*3))”,exp1,op,exp2); exp1 // “1”; 操作 // '+' exp2 // "(2*3)"; </前> ## 约束条件 - <var>1 \leq |E| \leq 100</var> - <var>E</var> 是一个表达式 ## 输入 <pre class="io-style" style="font-size:16px"><var>E</var> </前> ## 输出 请将表达式<var>E</var>的计算结果输出在一行上。 <h5>输入示例1</h5> <前>(1+2) </前> ##### 输出示例 1 <前>3 </前> ##### 输入示例 2 <前>((1+2)*3) </前> ##### 输出示例 2 <前>3 </前> ##### 输入示例 3 <前>((1+2)+3) </前> ##### 输出示例 3 <前>6 </前> ## 提示 <详情> <summary>点击打开提示</summary> - 看表达式的定义,是一个递归定义 - 将“接收表达式并返回计算结果”的函数实现为递归函数 - 由整数组成的表达式对应于基本情况 - 加法和乘法表达式对应于递归步骤 </详情> ## 答案示例 **一定要自己考虑后再检查**。 <详情> <summary>点击打开示例答案</summary> <pre class="prettyprint linenums source-code">#include <bits/stdc++.h>; 使用命名空间 std; // stoi(s) ...将字符串 s 转换为整数 // 从以下形式的表达式中提取表达式1、运算符、表达式2 (表达式1 运算符表达式2) void extract(字符串 e, 字符串 &amp;exp1, char &amp;op, 字符串 &amp;exp2) { int 嵌套 = 0; // 表达式嵌套级别 整数 i = 1; // 从'('之后开始读取 // 查找运算符 for (; i < e.size(); i++) { if (e.at(i) == '(') 嵌套++; if (e.at(i) == ')') 嵌套 --; if ((e.at(i) == '+' || e.at(i) == '*') &amp;&amp; 嵌套 == 0) { op = e.at(i); 打破; } } // s.substr(i, len) ...从 s 的第 i 个字符返回 len 个字符 exp1 = e.substr(1, i); exp2 = e.substr(i+1, e.size()-i); } int calc_expression(字符串 e) { // 基本情况(整数表达式) if (e.at(i) != '(') { // 将 e 解释为整数 返回斯托伊(e); } // 递归步骤 字符串 exp1, exp2; 字符操作; 提取(e,exp1,op,exp2); // 从 e 中提取表达式 1 运算符('+' 或 '*')表达式 2 // 计算 int l = calc_表达式(exp1); int r = calc_表达式(exp2); 整数 ans = 0; 如果(操作=='+'){ ans = l + r; // 加法 } 否则{ ans = l * r; // 乘法 } 返回答案; } int main() { 字符串 E; 辛>> E; 计算<<计算表达式(E) <<结束; } </前> </详情> ---

报告传输时间示例

下一个问题与迄今为止介绍的示例不同,并且是除非使用递归函数实现否则会变得复杂的示例。

难度较高,思考后如果不明白,请看提示和答案示例。

問題文

您是A公司的总裁。 A公司是 它由N组织组成,每个组织都有自己的 来自编号0它的编号为N - 1。 编号为 0的组织是顶级组织。

组织之间存在父子关系。0以外N - 1组织始终有一个父组织。 可以有多个子组织。 此外,每个组织都与最高组织直接或间接相关。

您要求所有组织提交报告。
为了避免拥塞,请重复“当每个组织完成其子组织的报告时,它会添加自己的报告并将其发送到父组织。”的过程。 没有任何附属组织的组织将立即仅将自己的报告发送给上级组织。

假设组织发送报告并由其上级组织接收需要 1 分钟。
当您一次开始传输所有报告时,找出所有组织的所有报告都传送到顶级组织的时间(传输开始后多少分钟)。 请注意,各机构的报告均已准备就绪,因此除了传送报告外,不会耗费任何时间。 编号为

制約

  • 1 \leq N \leq 50
  • 0 \leq p_i < i (1 \leq i \leq N - 1)

入力

N
p_1 p_2 \ldots p_{N - 1}

p_i是i的组织的上级组织是 表示该组织是p_i。 请注意,编号为 0的组织是顶级组织,没有父组织。

出力

T

当所有报告开始同时传输时,所有组织的报告都集中到最高组织下的时间。T(从一开始T分钟后)一行。


入力例1
6
0 0 1 1 4
実行結果
3

在此输入示例中,组织具有以下关系: 编号为

  • 1的组织的上级组织是0番
  • 2的组织的上级组织是0番
  • 3的组织的上级组织是1番
  • 4的组织的上级组织是1番
  • 5的组织的上级组织是4番

这种关系如下图所示。 (箭头从子组织指向父组织。)

在下图中,子组织完成报告的时间(收集的报告发送到父组织的时间)以蓝色文本显示,从每个子组织收到报告的时间以红色文本显示。

从该图中可以看到,在顶级组织下收集所有组织报告的时间为 3。


这个问题中的类似组织的结构称为树结构。 处理树结构时,递归函数通常很有用。

示例程序

请重写下面的示例程序并完成该程序,使其行为如下一张幻灯片所示。
幻灯片显示了输入示例 1 的图像。

#include <bits/stdc++.h>
using namespace std;

// x番の組織について、子組織からの報告書が揃った時刻を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int complete_time(vector<vector<int>> &children, int x) {
  // (ここに追記して再帰関数を実装する)
}

// これ以降の行は変更しなくてよい

int main() {
  int N;
  cin >> N;

  vector<int> p(N);  // 各組織の親組織を示す配列
  p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
  for (int i = 1; i < N; i++) {
    cin >> p.at(i);
  }

  // 組織の関係から2次元配列を作る(理解しなくてもよい)
  vector<vector<int>> children(N);  // ある組織の子組織の番号一覧  // N×0の二次元配列
  for (int i = 1; i < N; i++) {
    int parent = p.at(i);  // i番の親組織の番号
    children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
  }

  // 0番の組織の元に報告書が揃う時刻を求める
  cout << complete_time(children, 0) << endl;
}

push_back是向数组添加元素的操作。关于这一点,请参见1.13.配列”。

関数complete_time的参数children是一个二维数组, 编号为 x的组织的子组织编号表的排列是 你可以通过children.at(x)得到它。

对于输入示例 1children的内容如下表所示。

x children.at(x)
0 {1, 2}
1 {3, 4}
2 {}
3 {}
4 {5}
5 {}

通过执行以下操作 您可以处理编号为x的组织的子组织。

for (int c : children.at(x)) {
  // (cについての処理)
}

提示

点击打开提示 - 「組織x下属组织报告完成时间"=组织x的所有子组织 关于c“从c收到报告的时间”的最大值 - “组织c“收到报告的时间”=“组织c报告完成时间”+1 - 对于没有附属机构的机构,报告完成时间为0。

解答例

我自己思考后,请务必检查。

单击打开示例答案
#include <bits/stdc++.h>
using namespace std;

// x番の組織について、子組織からの報告書が揃う時刻を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int complete_time(vector<vector<int>> &children, int x) {
  // ベースケース
  if (children.at(x).size() == 0) {
    return 0;  // 子組織が無いような組織について、報告書が揃う時刻は0
  }

  // 再帰ステップ
  int max_receive_time = 0;  // 受け取った時刻の最大値
  // x番の組織の子組織についてループ
  for (int c : children.at(x)) {

    // (子組織 c のもとに揃った時刻 + 1) の時刻に c からの報告書を受け取る
    int receive_time = complete_time(children, c) + 1;

    // 受け取った時刻の最大値 = 揃った時刻 なので最大値を求める
    max_receive_time = max(max_receive_time, receive_time);
  }
  return max_receive_time;
}

// これ以降の行は変更しなくてよい

int main() {
  int N;
  cin >> N;

  vector<int> p(N);  // 各組織の親組織を示す配列
  p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
  for (int i = 1; i < N; i++) {
    cin >> p.at(i);
  }

  // 組織の関係から2次元配列を作る
  vector<vector<int>> children(N);  // ある組織の子組織の番号一覧
  for (int i = 1; i < N; i++) {
    int parent = p.at(i);  // i番の親組織の番号
    children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
  }

  // 0番の組織の元に報告書が揃う時刻を求める
  cout << complete_time(children, 0) << endl;
}
入力例1
6
0 0 1 1 4
実行結果
3
入力例2
8
0 1 2 1 4 3 1
実行結果
4
入力例3
10
0 0 1 3 2 5 3 4 6
実行結果
4

注意点

堆栈溢出

递归调用是一个方便的功能,可以让你简洁地编写复杂的流程,但是 “当递归调用链持续太多次时,就会发生运行时错误。” 这一点你一定要注意。

例如,如果您在实现递归函数时犯了错误并最终导致无限递归调用,则会出现运行时错误。 而且,即使递归函数实现正确,在进行大量递归调用(数千万次)的程序中, 可能会出现运行时错误。

以下程序是一个示例,未实现基本情况,因此无法正常工作。

#include <bits/stdc++.h>
using namespace std;

// 0からnまでの総和を計算し、途中結果を出力する
int sum(int n) {
  // ベースケースが実装されていないので止まらない!

  // 再帰ステップ
  int result = sum(n - 1) + n;
  cout << "sum(" << n << ") = " << result << endl;  // 途中結果を出力する
  return result;
}

int main() {
  // 無限に再帰呼び出しが起こる
  cout << sum(100) << endl;
}
执行结果示例
退出代码 139
実行時間 218 毫秒
内存 263296 KB

退出代码 139 表示程序未正确终止。

在更高级的层面上,进行函数调用时会消耗内存。 运行程序的计算机的内存是有限的,因此过多的递归调用会耗尽内存。 如果内存不足,则无法执行更多程序,并且会出现运行时错误。 这种现象 它被称为堆栈溢出。 如果运行代码测试时得到退出代码 139,则怀疑堆栈溢出。

实现递归函数时,请记住过多的递归调用可能会导致运行时错误。 您可能还需要重写循环语法中的迭代以避免堆栈溢出。


详情

相互再帰

两个或多个函数以递归方式相互调用。相互再帰。

看下面的程序。 请参阅

#include <bits/stdc++.h>
using namespace std;

// プロトタイプ宣言 (1.15.関数「細かい話」を参照)
bool is_even(int);
bool is_odd(int);

// nが偶数かを判定する
bool is_even(int n) {
  // ベースケース
  if (n == 0) {
    return true;
  }
  // 再帰ステップ
  return is_odd(n - 1);  // n-1 が奇数なら、nは偶数
}
// nが奇数かを判定する
bool is_odd(int n) {
  // ベースケース
  if (n == 0) {
    return false;
  }
  // 再帰ステップ
  return is_even(n - 1);  // n-1 が偶数なら、nは奇数
}

int main() {
  cout << is_even(4) << endl;  // 1
  cout << is_odd(5) << endl;   // 1
  cout << is_even(3) << endl;  // 0
}
実行結果
1
1
0

首先, 如果is_even。在递归步骤中 呼叫is_odd。 另一方面 在is_odd的递归步骤中 呼叫is_even。

相互递归调用“在该函数之后定义的另一个函数”,因此需要原型声明。 关于原型声明, 有关详细信息,请参阅1.15.関数。

对于上述程序,is_even首先定义,所以is_odd的原型声明就足够了,但为了清楚起见,我已经编写了两个原型声明。

相互递归使程序运行变得复杂,但是 与普通的递归函数一样,如果满足“递归调用链有一个结束”的条件,它将起作用。

高级示例

中间输出示例

点击打开 在下面的程序中,递归函数“func”是一个“将参数 n 减 1,执行递归调用直到 n=0,并输出调用堆栈”的函数。 这有点复杂,但请跟随我们看看它是如何完成的。
#include <bits/stdc++.h>
using namespace std;

// num個分のスペースからなる文字列を返す (字下げに用いる)
string space(int num) {
  string ret = "";
  for (int i = 0; i < num; i++) {
    ret += " ";
  }
  return ret;
}

// 呼び出しの深さに応じて字下げし、関数の開始時点であるというメッセージを出力
void print_in(int n, int depth) {
  cout << space(depth * 4) << "func(" << n << ", " << depth << ") in" << endl;
}

// 呼び出しの深さに応じて字下げし、関数の終了時点であるというメッセージを出力
void print_out(int n, int depth) {
  cout << space(depth * 4) << "func(" << n << ", " << depth << ") out" << endl;
}

// n: 何回の再帰呼出しを行うか
// depth: 呼び出しの深さ(何回目の再帰呼び出しか)
void func(int n, int depth) {
  // ベースケース
  if (n == 0) {
    print_in(n, depth);   // 開始
    print_out(n, depth);  // 終了
    return;
  }

  // 再帰ステップ
  print_in(n, depth);  // 開始
  func(n - 1, depth + 1);  // 残り回数を1減らし、呼び出しの深さを1増やす
  print_out(n, depth); // 終了
}

int main() {
  func(3, 0);  // 3回の再帰呼び出しを行う, 初めの深さを0とする
}
実行結果
func(3, 0) in
    func(2, 1) in
        func(1, 2) in
            func(0, 3) in
            func(0, 3) out
        func(1, 2) out
    func(2, 1) out
func(3, 0) out

更改参数数组的示例

点击打开 考虑以下问题。

示例:探索网格上的迷宫

N \times N有一个正方形网格。 从上面i行,从左起j选择列中的方块。 我们将其表示为(i - 1, j - 1 )。 创建一个程序,将网格视为迷宫,从起点开始移动,并确定是否可以到达目标。 开始是(0, 0)目标是 比方说(N - 1, N - 1)。 正方形有两种类型,每个正方形都是其中一种类型。 - 墙方格:你不能移动到那个方格。 - 通道空间:你可以移动到该空间。 一开始玩家 我在(0, 0)。 假设(0, 0)、(N - 1, N - 1)始终是过道正方形。 玩家可以从上、下、左、右四个方向移动到与当前所在方格相邻的方格中的任意一个通道方格。 它不能沿对角线移动或进入墙壁空间。另外,N \times N你不能移动到方块范围之外。 通过重复动作到达目标方块 编写一个程序,如果可以到达(N - 1, N - 1),则输出“Yes”,否则输出“No”。 每个方块的类型以字符串数组的形式输入,其中“.”代表通道方块,“#”代表墙壁方块。 第一行是迷宫的大小。 输入N,从第二行开始进入迷宫方块。
入力例1
3
.##
...
##.
出力例1
Yes
这个迷宫是 通过移动(0, 0)→(1, 0)→(1, 1)→(1, 2)→(2, 2)就可以达到目标,所以输出“Yes”。
入力例2
4
.###
.###
.###
#...
出力例2
No
另外,在下一个迷宫中,无法从起点移动到目标,因此输出“No”。
单击打开输入/输出示例
入力例3
3
...
##.
##.
出力例3
Yes
入力例4
5
....#
...#.
..#..
.#...
#....
出力例4
No
入力例5
10
..#.#..###
.###.#.##.
.##....#..
.##..#....
....#.##..
#####.....
##.#.###.#
#..#.##..#
...####.##
#.#.###...
出力例5
Yes

解説

当处理像这样的网格上的移动时,很难编写简单的循环语法。 然而,使用递归函数编写相对容易。

解答例
#include <bits/stdc++.h>
using namespace std;

// 正しい移動かを調べる (y, x)が移動先
bool is_valid_move(vector<string> &board, vector<vector<bool>> &checked, int x, int y) {
  int N = board.size();

  // 移動先がマス目の外である場合
  if (x <= -1 || x >= N || y <= -1 || y >= N) {
    return false;
  }
  // 移動先が壁マス
  if (board.at(y).at(x) == '#') {
    return false;
  }
  // 既に調べているマスへの移動は調べないのでfalseを返す
  if (checked.at(y).at(x)) {
    return false;
  }

  // それ以外なら正しい移動
  return true;
}

// (y, x)にいる状態からゴールに到達できるか
// board: マス目の種類
// checked: そのマスを既に調べたかを持つ二次元配列
bool reachable(vector<string> &board, vector<vector<bool>> &checked, int x, int y) {
  int N = board.size();

  // ベースケース
  if (x == N - 1 && y == N - 1) {
    // ゴールにいる状態
    return true;
  }

  // 再帰ステップ

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく

  // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか?
  bool result = false;

  // 上へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) {
    result = true;
  }
  // 右へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) {
    result = true;
  }
  // 下へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) {
    result = true;
  }
  // 左へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) {
    result = true;
  }

  return result;
}

int main() {
  int N;
  cin >> N;
  // マス目の状態を受け取る
  vector<string> board(N);
  for (int i = 0; i < N; i++) {
    cin >> board.at(i);
  }

  // 既にそのマスを調べたかを保持する二次元配列
  vector<vector<bool>> checked(N, vector<bool>(N, false));  // false(まだ調べていない)で初期化しておく

  // (0, 0) からゴールまで到達できるか?
  if (reachable(board, checked, 0, 0)) {
    cout << "Yes" << endl;
  }
    else {
    cout << "No" << endl;
  }
}

is_valid_move函数是判断是否可以移动到某个方格的函数。 我们检查是否有超出范围的运动或向墙壁空间的运动。

reachable该函数是一个递归函数,是一个检查从某个方格是否可以到达目标的函数。

基本情况如下。

  if (x == N - 1 && y == N - 1) {
    // ゴールにいる状態
    return true;
  }

返回 true,因为目标已达到。

递归步骤如下所示:

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく

  // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか?
  bool result = false;

  // 上へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) {
    result = true;
  }
  // 右へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) {
    result = true;
  }
  // 下へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) {
    result = true;
  }
  // 左へ移動したマスからゴールに到達できるか?
  if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) {
    result = true;
  }

  return result;

检查你是否可以上下左右移动,如果可以移动,检查你是否可以从你移动的地方到达目标。

为了防止无限循环,需要确保已经检查过一次的方块不会被再次检查。

如果你可以从方格 A 移动到相邻的方格 B,那么你也可以从 B 移动到 A。 如果你可以检查一个已经被检查过的正方形, 为了找出“是否可以从a到达目标?”,检查“是否可以从b到达目标?”,然后再次检查“是否可以从a到达目标”......如此循环,发生无限循环。

vector<vector<bool>> checked表示是否已经检查过N \times N的二维数组。 这可以防止已经检查过的细胞被检查。

这样,可以在更改参数数组时进行递归调用。


演習問題

请解决链接目的地的问题。

ABC/ARC问题

我们将介绍AtCoder初学者竞赛/AtCoder常规竞赛的过去问题,可以用到目前为止的知识解决。 如果您对练习题不满意,请尝试一下。

我们准备了提示和示例答案。请参考一下。

点击打开提示 首先,创建一个函数来检查“所有土地方块是否已连接”。 “所有陆地方块都是相连的”可以改写为“从一个陆地方块开始反复上下左右移动就可以到达所有陆地方块”。 这可以通过应用高级示例“探索网格上的迷宫”来进行研究。
vector<vector<bool>> checked(10, vector<bool>(10, false));

// 陸地マスを1つ探す
int y, x;
for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 10; j++) {
    if (board.at(i).at(j) == 'o') {
      y = i;
      x = j;
      break;
    }
  }
}
/* 引数: 盤面, チェック二次元配列, y座標, x座標*/
fill_island(board, checked, y, x);  // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする

bool ok = true;
for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 10; j++) {
    if (board.at(i).at(j) == 'o') {
      if (!check.at(i).at(j)) {
        // 到達できていない陸地マスがある
        ok = false;
      }
    }
  }
}

// ok == true なら全ての陸地マスは繋がっている
单击打开示例答案
#include <bits/stdc++.h>
using namespace std;

// (y, x)から到達できるすべての陸地マスのcheckedをtrueにする
void fill_island(vector<vector<char>> &board, vector<vector<bool>> &checked, int y, int x) {
  if (y < 0 || x < 0 || y >= 10 || x >= 10) return;
  if (board.at(y).at(x) == 'x') return;
  if (checked.at(y).at(x)) return;

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく
  fill_island(board, checked, y - 1, x    );  // 上
  fill_island(board, checked, y    , x + 1);  // 右
  fill_island(board, checked, y + 1, x    );  // 下
  fill_island(board, checked, y    , x - 1);  // 左
}

bool check_connected(vector<vector<char>> &board) {
  vector<vector<bool>> checked(10, vector<bool>(10, false));

  // 陸地マスを1つ探す
  int y, x;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (board.at(i).at(j) == 'o') {
        y = i;
        x = j;
        break;
      }
    }
  }
  /* 引数: 盤面, チェック二次元配列, y座標, x座標*/
  fill_island(board, checked, y, x);  // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする

  bool ok = true;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (board.at(i).at(j) == 'o') {
        if (!checked.at(i).at(j)) {
          // 到達できていない陸地マスがある
          ok = false;
        }
      }
    }
  }

  // ok == true なら全ての陸地マスは繋がっている
  return ok;
}

int main() {
  vector<vector<char>> board(10, vector<char>(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> board.at(i).at(j);
    }
  }

  for (int y = 0; y < 10; y++) {
    for (int x = 0; x < 10; x++) {
      if (board.at(y).at(x) == 'o') continue;
      // (y, x)は海のマス
      // ここを埋め立てたと仮定して、島が1つになるかを判定

      board.at(y).at(x) = 'o';  // 埋め立てたと仮定する

      if (check_connected(board)) {
        cout << "YES" << endl;
        return 0;
      }

      board.at(y).at(x) = 'x';  // 戻す
    }
  }

  cout << "NO" << endl;
}

这几乎与“探索网格上的迷宫”相同。

下面的问题与示例中处理的问题略有不同。 3.05.位运算 也可以通过使用中描述的按位穷举搜索来解决,无需递归函数。

上一页 | 下一页