有没有做阅读程序填空的好方法?

学习编程中的Ben · 发表于 2023-9-10 14:45:33

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

×

比如下面这个题:

对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 q 为第 i 个位置之后第一个比 P 值更大的位置，如果不存在这样的位置，则 q = n + 1。举例来说，如果 n = 5 且 P 为 1 5 4 2 3 ，则 q 为2 6 6 5 6。

下列程序读入了排列 P ，使用双向链表求解了答案。试补全程序。

#include <iostream>

using namespace std;

const int N = 100010;

int n;

int L[N], R[N], a[N];

int main() {

cin >> n;

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

      int x;

      cin >> x;

      ① ;

}

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

      R[i] = ② ;

      L[i] = i - 1;

}

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

      L[ ③ ] = L[a[i]];

      R[L[a[i]]] = R[ ④ ];

}

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

cout << ⑤ << " ";

}

cout << endl;

return 0;

}
复制代码

完全不会做呜呜呜
有谁可以给我讲一下做题思路吗?

isdkz · 发表于 2023-9-10 14:45:40

题目描述：

对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 q 为第 i 个位置之后第一个比 P 值更大的位置，如果不存在这样的位置，则 q = n + 1。举例来说，如果 n = 5 且 P 为 1 5 4 2 3 ，则 q 为2 6 6 5 6。

下列程序读入了排列 P ，使用双向链表求解了答案。试补全程序。

题目分析：

这道题目是一道模拟题，主要考察对双向链表的掌握以及对指针的运用。

思路：

1. 首先读入排列 P，将每个数存入数组 a 中，同时将每个数的左右指针初始化为 0。

2. 初始化每个数的右指针 R[ i] 为 i+1，左指针 L[ i] 为 i-1。

3. 对于每个数 a[ i]，将它的左指针的右指针指向它的右指针，右指针的左指针指向它的左指针。

4. 最后输出每个数的答案即可。

代码如下：

Mike_python小 · 发表于 2023-9-10 14:45:57

题目理解：
题目要求补全给定程序，该程序通过输入一个排列P，利用双向链表求解出答案q，并输出q的每个位置的值。

程序补全分析：
1. 在第一个for循环中，需要将输入的x插入到链表中的合适位置。可以使用双向链表的思想，将x插入到链表末尾，并更新链表L和R，使得L表示节点i的前一个节点编号，R表示节点i的后一个节点编号。需要注意的是，链表头节点的L值为0，链表尾节点的R值为n+1。

2. 在第二个for循环中，为链表中的每个节点设置初始值。由于链表中节点的顺序与排列P对应，因此可以根据排列P中的值来设置链表节点的R值。

3. 在第三个for循环中，需要根据排列P的值更新链表节点的L和R值。根据题目中的描述，L[a]表示排列P中值为a的元素的前一个位置，R[L[a]]表示排列P中值为a的元素的后一个位置。因此，在这个循环中，可以通过更新L和R数组来完成链表节点的更新。

4. 最后一个for循环用于输出答案q的每个位置的值，即输出R，其中i取值范围为1到n。

程序补全解法：
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;

for (int i = 1; i <= n; ++i) {
      int x;
      cin >> x;

      // 1. 将x插入到链表末尾
      a[i] = x;
      R[i - 1] = i;
      L[i] = i - 1;
}

for (int i = 1; i <= n; ++i) {
      // 2. 设置链表中的每个节点的初始值
      R[i] = i + 1;
      L[i] = i - 1;
}

for (int i = 1; i <= n; ++i) {
      // 3. 更新链表节点的L和R值
      L[R[a[i]]] = L[a[i]];
      R[L[a[i]]] = R[a[i]];
}

for (int i = 1; i <= n; ++i) {
      // 4. 输出答案q的每个位置的值
      cout << R[i] << " ";
}

cout << endl;

return 0;
}
复制代码

这样，程序补全完成后，即可求解出答案q，并按要求输出。

球一个最佳答案谢谢啦！这对我非常重要！

陶远航 · 发表于 2023-9-10 14:45:59

这是一道关于双向链表的填空题。下面是对应空缺处的填写思路：

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a[ i] = x; // 填充空白处①，将输入的数x保存到数组a中
}
for (int i = 1; i <= n; ++i) {
R[ i] = i + 1; // 填充空白处②，初始化R数组，使得每个位置的下一个位置为i+1
L[ i] = i - 1; // 填充空白处③，初始化L数组，使得每个位置的上一个位置为i-1
}
R[n] = n + 1; // 填充空白处④，将最后一个位置的下一个位置设为n+1
for (int i = 1; i <= n; ++i) {
L[R[a[ i]]] = L[a[ i]]; // 填充空白处③，将a[ i]的上一个位置设为L[a[ i]]
R[L[a[ i]]] = R[a[ i]]; // 填充空白处④，将a[ i]的下一个位置设为R[a[ i]]
}
for (int i = 1; i <= n; ++i) {
cout << R[ i] << " "; // 填充空白处⑤，输出R数组的值
}
cout << endl;
return 0;
}

复制代码

填空思路解析：
1. 在第一个 for 循环中，将输入的数 x 保存到数组 a 中，填充空白处①。在排列 P 的第 i 个位置，将第 i 个输入保存到 a[ i] 中。
2. 在第二个 for 循环中，初始化 R 数组和 L 数组，填充空白处②和③。R 数组表示当前位置的下一个位置，L 数组表示当前位置的上一个位置。初始时，R 数组的值设为 i+1，L 数组的值设为 i-1。
3. 在第三个 for 循环中，遍历排列 P。通过修改 L 数组和 R 数组，来更新每个位置的上一个位置和下一个位置。对于排列 P 的第 i 个位置，将 a[ i] 的上一个位置设为 L[a[ i]]，将 a[ i] 的下一个位置设为 R[a[ i]]。
4. 最后一个 for 循环中，输出 R 数组的值，填充空白处⑤，即输出每个位置的下一个位置。

这样，运行完该程序，就可以得到所需的 q 数组。

希望这个解析能够帮助到你！如有更多问题，请随时提问。
如果问题已经解决，请设置最佳答案

Mike_python小 · 发表于 2023-9-10 15:10:05

还有六天考试

liuhongrun2022 · 发表于 2023-9-10 15:13:13

chatgpt所做，但是测试后正确

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a[i] = x;
}
for (int i = 1; i <= n; ++i) {
int q = n + 1;
for (int j = i + 1; j <= n; ++j) {
if (a[j] > a[i]) {
q = j;
break;
}
}
R[i] = q;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[R[i]] = L[i];
R[L[i]] = R[i];
}
for (int i = 1; i <= n; ++i) {
cout << R[i] << " ";
}
cout << endl;
return 0;
}

复制代码

学习编程中的Ben · 发表于 2023-9-10 15:45:10

liuhongrun2022 发表于 2023-9-10 15:13
chatgpt所做，但是测试后正确

不是正确答案

学习编程中的Ben · 发表于 2023-9-10 15:52:01

Mike_python小发表于 2023-9-10 15:10
还有六天考试

空一:
正确答案： a[x] = i

你的ChatGPT有问题

Mike_python小 · 发表于 2023-9-10 16:20:32

学习编程中的Ben 发表于 2023-9-10 12:52
空一:
正确答案： a[x] = i

嗯

账号		自动登录	找回密码
密码			立即注册

[问题求助] 有没有做阅读程序填空的好方法?

马上注册，结交更多好友，享用更多功能^_^