优质牛肋骨
本文最后更新于 707 天前,其中的信息可能已经有所发展或是发生改变。

Original Link

思想

  • DFS
  • 从小到大依次枚举所有的数显然不现实,因此考虑按位枚举。
  • 枚举从最高位开始,之后枚举每一位的数,直到达到指定位数为止。
  • 枚举每一位后,需要判断当前位的数和高位数的组合数是否为质数,只有如此才能满足条件。
  • 举例说明对于 73317331 的枚举过程:
    • 第一位为 77,是质数,枚举下一位;
    • 第二位为 33,和高位数组合为 7373 是质数,枚举下一位;
    • 第三位为 33,和高位数组合为 733733 是质数,枚举下一位;
    • 第四位为 11,和高位数组合为 73317331 是质数,达到了位数条件即为所求。
  • 由上述例子可知,最高位必定取值为 {2,3,5,7}\set{ 2, 3, 5, 7 },且后续添加的数不能为偶数(从 11 枚举到 99 后续再判断也可以)。
  • 因此,递归的每一层,枚举剩余位从 00 开始枚举到 99 与高位数组合判断。
  • 若组合数为质数,则递归到下一层,否则跳过。
  • 最终满足的组合数直接输出即可。

代码1(数组存方案版)

#include <bits/stdc++.h>
using namespace std;
int n;
int pos[] = {2, 3, 5, 7}; //最高位必为其中之一
int add[] = {1, 3, 5, 7, 9};
int ans[10]; // 存储组合数的每一位
bool is_prime(int x){ // 判断是否为质数
if(x < 2) return 0;
for(int i = 2; i <= x / i; i ++){
if(x % i == 0) return 0;
}
return 1;
}
int sum(int u, int x){ // 求高位数的和
int t = 0;
for(int i = 0; i < u; i ++){ // 循环叠加组合高位数
t = t * 10 + ans[i];
}
return t * 10 + x;
}
void dfs(int u){
if(u == n){ // 满足位数输出
for(int i = 0; i < u; i ++) cout << ans[i];
cout << endl;
return ;
}
for(int i = 0; i < 5; i ++){
if(is_prime(sum(u, add[i]))){ // 满足和高位数组合为质数
ans[u] = add[i]; // 将当前位记录
dfs(u + 1); // 枚举下一位
}
}
}
void solve(){
cin >> n;
for(int i = 0; i < 4; i ++){
ans[0] = pos[i]; // 最高位
dfs(1); // 从最高位的下一位开始枚举
}
}
int main(){
solve();
return 0;
}

代码2(优化空间版)

#include <bits/stdc++.h>
using namespace std;
int n;
int pos[] = {2, 3, 5, 7};
int add[] = {1, 3, 5, 7, 9};
bool is_prime(int x){
if(x < 2) return 0;
for(int i = 2; i <= x / i; i ++){
if(x % i == 0) return 0;
}
return 1;
}
void dfs(int u, int ans){ // 将答案直接用 ans 表示
if(u == n){
cout << ans << endl;
return ;
}
for(int i = 0; i < 5; i ++){
int t = ans * 10 + add[i]; // 和高位数的组合数
if(is_prime(t)) dfs(u + 1, t); // 满足为质数递归枚举下一位
}
}
void solve(){
cin >> n;
for(int i = 0; i < 4; i ++) dfs(1, pos[i]); // 最高位从 pos[i] 开始,即 ans = pos[i]
}
int main(){
solve();
return 0;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇