有一个集合M是这样生成的:
(1) 已知 k 是集合 M 的元素;
(2) 如果 y 是 M 的元素,那么, 2y+1 和 3y+1 都是 M 的元素;
(3) 除了上述二种情况外,没有别的数能够成为 M 的一个元素。
任意给定 k 和 x,请判断 x 是否是 M 的元素。
如果是,则输出YES,否则,输出 NO
样例输入
0
22
样例输出
YES
- 思路:对k不断进行操作,即运算2k+1和3k+1,判断操作后得到的数是否等于x;
- 如果经过未知次的操作后,k=x,等于说明x可以放进集合;
- 如果x比k小,则不能放入集合,因为集合里放的是2k+1、3k+1之类的数;
C语言描述:
#include <stdio.h> #include <stdbool.h> // 判断 x 是否是集合 M 的元素 bool isElementOfM(int k, int x) { // 创建一个布尔型数组,用来记录集合 M 中的元素 bool dp[x + 1]; // 初始化数组,将所有元素标记为 false for (int i = 0; i <= x; i++) { dp[i] = false; } // 将 k 标记为集合 M 的元素 dp[k] = true; // 从 k 开始递推生成集合 M 中的元素 for (int i = k; i <= x; i++) { // 如果当前元素是集合 M 中的元素 if (dp[i]) { // 根据规则 2,生成 2i+1 和 3i+1,并标记为集合 M 的元素 if (2 * i + 1 <= x) { dp[2 * i + 1] = true; } if (3 * i + 1 <= x) { dp[3 * i + 1] = true; } } } // 返回 x 是否是集合 M 的元素 return dp[x]; } int main() { int k, x; // 输入 k 和 x printf("请输入 k 和 x:"); scanf("%d %d", &k, &x); // 判断 x 是否是集合 M 的元素,并输出结果 if (isElementOfM(k, x)) { printf("YES\n"); } else { printf("NO\n"); } return 0; }
汇编语言:
include irvine32.inc .data x DWORD ? k DWORD ? yesMsg BYTE "YES", 0 noMsg BYTE "NO", 0 .code dfs PROC mov eax, [esp+4] ; 获取函数参数 k cmp eax, x ; 比较 k 和 x jg L1 ; 如果 k > x,返回 false je L2 ; 如果 k == x,返回 true ; 递归调用 mov eax, [esp+4] imul eax, 3 inc eax push eax call dfs test al, al jnz L2 mov eax, [esp+4] imul eax, 2 inc eax push eax call dfs test al, al jnz L2 jmp L1 L1: mov eax, 0 ; 返回 false ret L2: mov eax, 1 ; 返回 true ret dfs ENDP main PROC mov edx, OFFSET k call ReadInt ; 读取 k mov k, eax mov edx, OFFSET x call ReadInt ; 读取 x mov x, eax push k call dfs ; 调用 dfs 函数 test al, al jnz L3 mov edx, OFFSET noMsg call WriteString jmp L4 L3: mov edx, OFFSET yesMsg call WriteString L4: call Crlf exit main ENDP END main
运行结果: