边城

用户名：uq_10486990894

访问量：782

签　名：

等　　级
排　　名	13796
经　　验	908
参赛次数	7
文章发表	1
年　　龄	20
在职情况	学生
学　　校	盐城师范学院
专　　业	数字媒体

　　自我简介：

TA的其他文章

特殊的质数肋骨啥也不会也能看的懂（二维vector）可用二维数组替代超详细讲解
浏览：677

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

优质题解

特殊的质数肋骨啥也不会也能看的懂（二维vector）可用二维数组替代超详细讲解

　　作者: 边城　　　　发表时间：2021-11-24 23:05:33 浏览：677　|　评论：0　

原题链接：蓝桥杯算法提高VIP-特殊的质数肋骨

###### 原题链接
[题目 1544: 蓝桥杯算法提高VIP-特殊的质数肋骨](https://www.dotcpp.com/oj/problem1544.html "题目 1544: 蓝桥杯算法提高VIP-特殊的质数肋骨")

######  题意解读
有一组肋骨  我们暂定有四根肋骨   每根肋骨上有一个数字    
好现在我们假定有四根肋骨了    数字为  7 3 3 1
我现在要拿走卖掉 每次拿一根 从右边1拿走      
现在要求我从右到左每拿走一块肋骨 剩下的肋骨组成的数都要是质数
比如一开始我什么也没拿 也要是质数 （7331）
拿走一块1   还剩733       733仍要是质数
再拿走一块3  还剩73       73是质数
拿走3   还剩7   7 是质数
题目要求肋骨根数为N时  求出所有的*符合条件的数*（长度为N） 
----这个数就是和一开始 7331 （长度为4） 一样的 砍砍砍一直都是是质数

###### 解法思路分析
根据分析 每次去掉一个数 都要剩下的数为质数   那我们反过来思考：
就在已有的质数 例如个位数的质数（0-9内）  
在这个质数后面加一位数字  生成一个质数 那么这个数就可以抗住砍一刀  （咳咳，就是去掉一个数）   同理 继续生成质数 可以抗住更多的刀

例如：7  是质数    那么我添一个3 在后面   那么现在生成了73  73是质数  
去掉3也是质数  那么我们就初步成型了   就用这个思路  我先把1位的素数加数字把所有的两位质数举出来  然后再用所有生成的两位质数 添1位数字在后面 生成所有符合条件的三位质数
（例如  73添一个3  构成733  或者添一个9  构成739   都为质数 且扛刀）
以此类推  推出所有的8位特殊质数（N<=8）。

那我们要考虑生成的过程了：   
首先当N=1 时  直接输出 2 3 5 7 （题中标注1不为质数） 程序结束。
N不为1时，我们就要细细打量打量这个数的构成了。
例如这个代表数的八位  v1  v2  v3  v4  
我们判断的有  v1v2v3v4   v1v2v3   v1v2  v1  这四个数是否符合条件
前三个是我们推出来的  基于v1 推出来。
那么v1  有哪些呢      很显然 一位质数 2,3,5,7   （题中标注1不为质数）
然后后面添数   有:
0 1 2 3 4 5 6 7 8 9
理论上是能添这么多数的的 但是添上0 2 4 6 8   新数就能被2整除  所以不考虑这几个数   其次 也不能添5 添5新数就能被5整除  
那么剩下的就是 1,3,7,9  这四个数。

###### 总结思路
根据2,3,5,7  轮流添加1,3,7,9中的一个 构成 二位质数  判断是否为质数  是则保留
二位质数处理完后 轮流添加1,3,7,9中的一个  构成三位质数  判断  存储    
三位有了，，以此类推   八位质数全部要生成完毕

###### 代码

```cpp
#include<iostream>
#include<vector>
using namespace std;

bool prime(int a)
{
	if(a<2)
	return false;
	for(int i=2;i*i<=a;i++)
	{
		if(a%i==0)
		return false;
	}
	return true;
}//判断是否为质数

int main()
{
	vector<vector<int> > a(9);//二维vector 存放生成的质数 可用数组替换  a[9][1000]  行标是几就存几位数的特殊质数   例如7331 存在a[4]数组里
	int n;
	int fir[4]={2,3,5,7};//一位质数  初始值
	int b[4]={1,3,7,9};//用来添加的数的数组  都在这呢
	cin>>n;
	if(n==1)
	{
		cout<<3<<endl<<5<<endl<<7<<endl;
		return 0;
	}//n=1 直接输出得了  不算了

a[1].insert(a[1].begin(),fir,fir+4);//把一位质数放在a[1]里面 要开始操作了

for(int t=2;t<9;t++)  //生成二位质数了  一直生成到8位
	{
		for(int j=0;j<a[t-1].size();j++)  //遍历a[t]数组中的每一个值 有值就抓出来生成新数
		{
			for(int i=0;i<4;i++)//把刚刚抓出来的数 依次添上1,3,7,9 生成新数
			{
				int neww=a[t-1][j]*10+b[i];//neww  你就是新数了
				if(prime(neww))
				{
					a[t].push_back(neww);//新来的 你是质数就存进去 不是就不存你
				}
			}
		}
	}

for(int i=0;i<9;i++)
    {
		a[i].resize(100);
	}//给vector设个长度  因为开始只设了9行    给它设长度  就能当数组用了

for(int j=0;j<100;j++)
		if(a[n][j]!=0)
		cout<<a[n][j]<<endl;		
}//题目要几位（n）的数 我就输出a[n]数组中的数

```

0.0分

18 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

边城

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

特殊的质数肋骨啥也不会也能看的懂（二维vector）可用二维数组替代超详细讲解

评论区

精彩推荐

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

成绩转换（C语言代码）

妹子杀手的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Quadratic Equation （C语言代码）

最好的，

孤独的骑士（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

边城

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

特殊的质数肋骨 啥也不会也能看的懂 （二维vector） 可用二维数组替代 超详细讲解

评论区

精彩推荐

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

成绩转换 （C语言代码）

妹子杀手的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Quadratic Equation （C语言代码）

最好的，

孤独的骑士 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

特殊的质数肋骨啥也不会也能看的懂（二维vector）可用二维数组替代超详细讲解

　　评论区

大神老白（C语言代码）

成绩转换（C语言代码）

妹子杀手的故事（C语言代码）

孤独的骑士（C语言代码）