边城

用户名：uq_10486990894

访问量：742

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

A+B for Input-Output Practice （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

优质题解

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

　　作者: 边城　　　　发表时间：2021-11-24 23:05:33 浏览：641　|　评论：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语言考试练习题_一元二次方程（C语言代码）

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

A+B for Input-Output Practice （C语言代码）

C二级辅导-求偶数和（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

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

评论区

精彩推荐

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

破解简单密码（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

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

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

字符串的输入输出处理（C语言代码）

Wu-求圆的面积（C++代码）

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

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

边城

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程 （C语言代码）

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

A+B for Input-Output Practice （C语言代码）

C二级辅导-求偶数和 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

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

评论区

精彩推荐

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

破解简单密码 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

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

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

字符串的输入输出处理 （C语言代码）

Wu-求圆的面积 （C++代码）

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

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

C语言考试练习题_一元二次方程（C语言代码）

C二级辅导-求偶数和（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

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

　　评论区

破解简单密码（C语言代码）

字符串的输入输出处理（C语言代码）

Wu-求圆的面积（C++代码）