Scratch编程一级 题库
迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。
时间限制: 1000
内存限制: 65536
输入
一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。
输出
左上角到右下角的最短路径, 格式如样例所示。
样例输入
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
样例输出
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
/*#include <iostream>*/
#include <bits/stdc++.h>
using namespace std;
const int idata = 50 + 5;
int maps[idata][idata];
bool judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int show[30];
bool flag;
void print(int tail) {
if (show[tail])
print(show[tail]);
cout << "(" << x[tail] << ", " << y[tail] << ")" << endl;
}
int main() {
int head, tail;
register int i, j;
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
cin >> maps[i][j];
if (maps[i][j] == 1)
judge[i][j] = 1;
}
}
head = 0;
tail = 1;
judge[0][0] = 1;
show[tail] = head;
while (tail > head) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !judge[nx][ny]) {
tail++;
x[tail] = nx;
y[tail] = ny;
judge[nx][ny] = 1;
show[tail] = head;
if (nx == 4 && ny == 4) {
flag = 1;
print(tail);
break;
}
}
}
if (flag)
break;
}
return 0;
}二叉树的深度
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
struct node {
int left, right;
} t[MAXN];
int n;
void build() {
for (int i = 1; i <= n; i++) {
cin >> t[i].left >> t[i].right;
}
}
#define rep1(i, n) for (int i = 1; i <= n; i++)
inline int dfs(int x) {
if (x == -1)
return 0;
return max(dfs(t[x].left), dfs(t[x].right)) + 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
build();
cout << dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}拼写检查
现在有一些英语单词需要做拼写检查, 你的工具是一本词典。 需要检查的单词, 有的是词典中的单词, 有的与词典中的单词相似, 你的任务是发现这两种情况。 单词 A 与单词 B 相似的情况有三种:
1、 删除单词 A 的一个字母后得到单词 B;
2、 用任意一个字母替换单词 A 的一个字母后得到单词 B;
3、 在单词 A 的任意位置增加一个字母后得到单词 B。
你的任务是发现词典中与给定单词相同或相似的单词。
时间限制: 2000
内存限制: 65536
输入
第一部分是词典中的单词, 从第一行开始每行一个单词, 以"#"结束。
词典中的单词保证不重复, 最多有 10000 个。 第二部分是需要查询的单词, 每行一个, 以"#"结束。 最多有 50 个需要查询的单词。 词典中的单词和需要查询的单词均由小写字母组成, 最多包含 15 个字符。
输出
按照输入的顺序, 为每个需要检查的单词输出一行。 如果需要检查的单词出现在词典中, 输出“?x is correct", ?x 代表需要检查的单词。
如果需要检查的单词没有出现在词典中, 则输出"?x: ?x1 ?x2 ...?xn",其中?x 代表需要检查的单词, ?x1...?xn 代表词典中与需要检查的单词相似的单词, 这些单词中间以空格隔开。 如果没有相似的单词, 输出"?x:"即可。
样例输入
i is has have be my more contest me too if award # me aware m contest hav oo or i fi mre #
样例输出
me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
bool IsSame(string a, string b) {
char drop;
// a短
int mi = min(a.length(), b.length());
string a1 = a;
string b1 = b;
sort(a1.begin(), a1.end());
sort(b1.begin(), b1.end());
bool exis = false;
for (int i = 0; i < mi; i++) {
if (a1[i] != b1[i]) {
drop = b1[i];
exis = true;
break;
}
}
if (!exis) {
drop = b1[b1.length() - 1];
}
string ti;
bool ex = false;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i]) {
ex = true;
ti = a.substr(0, i);
ti = ti + drop;
ti = ti + a.substr(i, 1000);
break;
}
}
if (!ex) {
ti = a + drop;
}
if (ti != b) {
return false;
} else {
return true;
}
}
int main() {
string dictionary[10010];
string words[60];
string a, b;
int dic = 0;
int m = 0;
while (1) {
cin >> a;
if (a == "#") {
break;
} else {
dictionary[dic++] = a;
}
}
while (1) {
cin >> b;
if (b == "#") {
break;
} else {
words[m++] = b;
}
}
for (int i = 0; i < m; i++) {
bool you = false;
for (int j = 0; j < dic; j++) {
if (dictionary[j] == words[i]) {
cout << words[i] << " is correct" << endl;
you = true;
break;
}
} // 判断是否完全相同。
if (you != true) {
cout << words[i] << ": ";
for (int j = 0; j < dic; j++) {
int somewhat = words[i].length() - dictionary[j].length();
if (somewhat == 0) {
for (int k = 0; k < words[i].length(); k++) {
if (words[i][k] != dictionary[j][k]) {
string tishen = words[i];
tishen[k] = dictionary[j][k];
if (tishen == dictionary[j]) {
cout << dictionary[j] << " ";
}
}
}
}
if (abs(somewhat) == 1) {
if (words[i].length() > dictionary[j].length()) {
if (IsSame(dictionary[j], words[i])) {
cout << dictionary[j] << " ";
}
} else {
if (IsSame(words[i], dictionary[j])) {
cout << dictionary[j] << " ";
}
}
}
}
cout << endl;
}
}
system("pause");
}数字变换
给定一个包含 5 个数字(0-9)的字符串, 例如 “02943”, 请将“12345”变换到它。 你可以采取 3 种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加 1。 如果加 1 后大于 9, 则变为 0
3. 将一个数字加倍。 如果加倍后大于 9,则将其变为加倍后的结果除以 10 的余数。
最多只能用第 2 种操作 3 次, 第 3 种操作 2 次 求最少经过多少次操作可以完成变换。
时间限制: 1000
内存限制: 65536
输入
有最多 100,000 组数据 每组数据就是包含 5 个数字的字符串
输出
对每组数据, 输出将"12345"变换到给定字符串所需要的最少操作步数。 如果无法变换成功, 输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多, 如果对每组数据都从头进行搜索, 就会超时。 建议先做预处理, 即以“12345” 作为初始状态做一遍彻底的广搜, 找出“12345” 经合法变换能够到达的所有字符串, 并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据, 在上述预处理记录的结果中进行查询即可。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define _init(x, v) memset(x, v, sizeof(x))
int rcd[100000];
bool vis[100000][5][5];
struct node {
int a[5], d, o2, o3;
};
queue<node> q;
void in() {
_init(rcd, -1);
node s = {1, 2, 3, 4, 5, 0, 3, 2};
q.push(s);
vis[12345][3][2] = 1;
rcd[12345] = 0;
}
int toNum(node &n) {
int t = 0;
for (int i = 0; i < 5; ++i) {
t *= 10;
t += n.a[i];
}
return t;
}
void bfs() {
while (!q.empty()) {
node s = q.front();
int t = toNum(s);
if (rcd[t] == -1 || rcd[t] > s.d)
rcd[t] = s.d;
// printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);
++s.d;
q.pop();
for (int i = 0; i < 5; ++i) {
// o1
if (i < 4 && s.a[i] != s.a[i + 1]) {
swap(s.a[i], s.a[i + 1]);
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
swap(s.a[i], s.a[i + 1]);
}
// o2
if (s.o2 > 0) {
--s.o2;
s.a[i] = (s.a[i] + 1) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = (s.a[i] + 10 - 1) % 10;
++s.o2;
}
// o3
if (s.o3 > 0) {
--s.o3;
int bak = s.a[i];
s.a[i] = (2 * s.a[i]) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = bak;
++s.o3;
}
}
}
}
int main() {
in();
bfs();
int n;
while (cin >> n) {
cout << rcd[n] << endl;
}
system("pause");
return 0;
}神奇的数列
一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后, 余下的元素会构成数列“2 8 9 6 94”
请问若要将该数列切割成若干个数据段, 则至少会切出来几个数据段?
样例: 按下列顺序切割数列“2 8 9 7 7 6 9 4” , 只要切割成 6 段
切割出“7 7” , 余下 “2 8 9 6 9 4”
切割出 “6” , 余下 “2 8 9 9 4”
切割出 “9 9” , 余下 “2 8 4”
切割出 “2” , 余下 “8 4”
切割出 “8” , 余下 “4”
时间限制: 1000
内存限制: 65536
输入
第一行是一个整数, 示共有多少组测试数据。 每组测试数据的输入包括两行: 第一行是整数 N, N<=200,表示数列的长度, 第二行是 N 个正整数。
输出
每个测试案例的输出占一行, 是一个整数。 格式是: Case n: x n 是测试数据组编号, x 是答案
样例输入
2 8 2 8 9 7 7 6 9 4 16 2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
样例输出
Case 1: 6 Case 2: 11
#include <cstring>
#include <iostream>
using namespace std;
int score[202][202];
int N;
int num[202];
int main() {
int T;
// cin >> T;
// freopen("C:\\Users\\csctest\\Desktop\\slin.txt", "r", stdin);
// freopen("C:\\Users\\csctest\\Desktop\\sloutx.txt", "w", stdout);
scanf("%d", &T);
int T0 = T;
while (T--) {
/*for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
score[i][j] = 256;
}
}*/
memset(score, 1, sizeof(score));
memset(num, 0, sizeof(num));
int N;
scanf("%d", &N); // cin >> N;
for (int i = 0; i < N; ++i) {
scanf("%d", &num[i]); // cin >> num[i];
score[i][i] = 1;
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
score[i][j] = 0;
}
}
for (int i = 0; i < N - 1; ++i) {
if (num[i] == num[i + 1])
score[i][i + 1] = 1;
else
score[i][i + 1] = 2;
}
for (int i = N - 2; i >= 0; --i) {
for (int j = i + 1; j < N; ++j) {
for (int k = i; k < j; ++k) {
if (num[k] == num[j]) {
score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j - 1]);
}
score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j]);
}
}
}
/*
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (score[i][j] < 10000 ) printf("%d ", score[i][j]);//cout
<< score[i][j] << " "; else printf("%d ", -1); //cout << -1 << " ";
}
printf("\n");//cout << endl;
}*/
printf("Case %d: %d\n", T0 - T, score[0][N - 1]);
// cout << "Case " << T0-T << ": " <<score[0][N-1] << endl;
}
return 0;
}硬币
宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。
时间限制: 1000
内存限制: 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。
#include <iostream>
using namespace std;
int val[210] = {0};
int ways[10000] = {0};
int ans[210] = {0};
int cal(int x, int y) {
if (x < 0)
return 0;
return ways[x] - cal(x - y, y);
}
int main() {
int N, Max;
cin >> N >> Max;
for (int i = 1; i <= N; ++i)
cin >> val[i];
ways[0] = 1;
for (int i = 1; i <= N; ++i)
for (int j = Max; j >= val[i]; --j)
ways[j] += ways[j - val[i]];
int cnt = 0;
for (int i = 1; i <= N; ++i)
if (cal(Max, val[i]) == 0)
ans[cnt++] = val[i];
cout << cnt << endl;
if (cnt == 0)
cout << ' ' << endl;
else {
cout << ans[0];
for (int i = 1; i < cnt; ++i)
cout << ' ' << ans[i];
}
return 0;
}公共子序列
我们称序列 Z = < z1, z2, ..., zk >是序列 X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >, 使得对 j = 1, 2, ... ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 现在给出两个序列 X 和 Y, 你的任务是找到 X 和 Y 的最大公共子序列, 也就是说要找到一个最长的序列 Z, 使得 Z 既是 X 的子序列也是 Y 的子序列。
时间限制: 3000
内存限制: 65536
输入
输入包括多组测试数据。 每组数据包括一行, 给出两个长度不超过200 的字符串, 表示两个序列。 两个字符串之间由若干个空格隔开。
输出
对每组输入数据, 输出一行, 给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
if (a > b)
return a;
else
return b;
}
int main() {
char s1[201], s2[201];
while (scanf("%s %s", s1, s2) != EOF) {
int dp[201][201];
memset(dp, 0, sizeof(dp));
int m = strlen(s1), n = strlen(s2);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}和数
给定一个正整数序列,判断其中有多少个数,等于数列中其他两个数的和。 比如,对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。
时间限制:10000
内存限制:65536
输入
共两行,第一行是数列中数的个数n ( 1 <= n <= 100),第二行是由n个不大于10000的正整数组成的数列,相邻两个整数之间用单个空格隔开。
输出
一个整数,即数列中等于其他两个数之和的数的个数。
样例输入
4
1 2 3 4
样例输出
2
#include <cstdio>
#include <iostream>
using namespace std;
int a[105];
int main() {
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
bool f = false;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (i != j && i != k && j != k && a[i] == a[j] + a[k]) {
f = true;
}
}
}
if (f == true)
ans++;
}
cout << ans;
return 0;
}分解因数
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a (1 < a < 32768)
输出
n行,每行输出对应一个输入。输出应是一个正整数,指明满足要求的分解的种数
样例输入
2 2 20
样例输出
1 4
#include <iostream>
using namespace std;
int cnt;
void fenjie(int x, int y) {
if (x == 1) {
cnt++;
return;
}
for (int i = y; i <= x; i++) {
if (x % i == 0) {
fenjie(x / i, i);
}
}
return;
}
int main() {
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> m;
cnt = 0;
fenjie(m, 2);
cout << cnt << endl;
}
return 0;
}丛林探险
一、准备工作
(1)删除默认小猫角色,添加角色:Avery Walking;
(2)添加背景:Bedroom 3、Jungle。
二、功能实现
(1)点击绿旗,初始背景为Bedroom 3,小女孩初始造型为avery walking-a,初始位置在舞台左侧,面向右方;

(2) 1秒后,小女孩从舞台左侧切换着造型移动到舞台右侧;

(3) 舞台切换为Jungle背景。


小鸟展翅
1.准备工作
(1)删除默认小猫角色,添加角色:Parrot;
(2)添加背景:Woods And Bench、Blue Sky。
2.功能实现
(1)点击绿旗,鹦鹉初始位置在舞台左侧,初始造型为“parrot-a”,初始背景为“Woods And Bench”;

(2)1秒后,播放声音Bird的同时,小鸟扇动翅膀向右侧飞行,一直飞行到舞台最右侧;

(3)背景切换为“Blue Sky”,鹦鹉重新回到左侧;

(4)继续飞行到舞台中间位置。


乌鸦喝水
1.准备工作
(1)添加背景:Desert;
(2)删除默认小猫角色,添加角色:Toucan、Glass Water。
2.功能实现
(1)乌鸦的初始位置在舞台左下角,面向右,水杯的初始位置在舞台右下角,如下图所示;

(2)乌鸦播放声音pop;
(3)乌鸦移动到水杯的位置,注意能看到移动过程;

(4)乌鸦到达水杯边上后,水杯切换为空造型。

答案解析:
乌鸦

水杯

评分标准:
(1)背景添加正确,角色添加正确;(2分)
(2)乌鸦和水杯的初始位置正确;(2分)
(3)水杯初始造型正确;(1分)
(4)能播放pop声音;(3分)
(5)乌鸦能水平向右移到水杯旁边,能看到移动过程;(5分)(看不到移动过程扣3分)
(6)乌鸦到达水杯旁边后,水杯切换为空杯造型。(2分)