数学专题，模拟
素数问题，普通筛和埃氏筛
bool judge(int x){
if(x<=1) return false;
int bound=(int)sqrt(x)+1;
//计算枚举上界，采用根号值取整后再加1
for(int i=2;i<bound;i++){
if(x%i==0) return false;
}
/*
或者直接for(int i=2,i*i<=n,i++) 会更省事
*/
return true;
}
//埃氏筛法
#include <iostream>
using namespace std;
//必须得要const int变量才可s
const int maxn=10001;
int prime[maxn],num=0;
bool p[maxn]={0};
void Find_Prime(){
for(int i=2;i<maxn;i++){
if(p[i]==false){
prime[num++]=i;
for(int j=i+i;j<maxn;j=j+i){
//倍数全都不是素数
p[j]=true;
}
}
}
}
int main()
{
int n;
Find_Prime();
while(cin>>n){
int count=0;
for(int i=0;i<maxn;i++){
if(prime[i]<n&&prime[i]%10==1){
count++;
cout<<prime[i];
if(i!=num-1)
cout<<" ";
}else if(prime[i]>=n)
break;
}
if(count==0) cout<<-1;
cout<<endl;
}
return 0;
}
另一种筛法，连续素数求和得超级素数
//超级素数要求是连续几个素数之和
//知识点：素数大表，计算小于N的素数并存储
//若N不是素数，返回结束
//若N是素数，用i，j对连续素数表进行遍历，若连续素数之和小于N
//j指针向后移动，累加求和，若连续素数之和大于N，将当前
//连续素数之和sum减去当前i指针指向素数，i指针向后移动
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;
bool vis[100000];
int prime[100000];
//素数打表部分
void init_prime(int n){
fill(vis,vis+100000,true);
vis[0]=vis[1]=false;
int num=0;
for(int i=2;i<=n;i++){
if(vis[i]==true){
num++;
prime[num]=i;
}
//j<=num保证prime[]存在,prime[]*i保证数字在n的范围内
for(int j=1;(j<=num)&&(i*prime[j]<=n);j++){
vis[i*prime[j]]=false; //prime[]倍数肯定不是素数
if(i%prime[j]==0){
break;
}
}
}
}
int main()
{
init_prime(100000);
int n;
cin>>n;
if(!vis[n]){
//若n不是素数，直接输出no，结束程序
cout<<"no"<<endl;
return 0;
}
int i=1,j=1,sum=0,count=0;
bool flag=false;
while(i<=j&&!flag){
sum+=prime[j]; //将i~j之间的素数求和
count++;
if(sum==n&&count>1){
flag=true;
break;
}else if(sum<n){
//如果连续素数之和小于n，则j往后移动
j++;
continue;
}
//sum超了的话，就移动i从小的减起
while(sum>n&&!flag&&count>1){
//连续素数之和大于n，减去i指针指向素数
sum=sum-prime[i];
count--;
if(sum==n&&count>1){
i++;
flag=true;
break;
}else if(sum<n&&count>1){
j++;
i++;
break;
}
i++;
//指针向后移动
}
}
if(flag){
cout<<"yes"<<endl;
int res=0;
for(int k=i;k<=j;k++){
cout<<prime[k]<<" ";
}
cout<<endl;
}else{
cout<<"no"<<endl;
}
return 0;
}
质因数
//埃氏筛法
#include <iostream>
#include <cmath>
using namespace std;
//必须得要const int变量才可s
const int maxn=1000001;
int prime[maxn],num=0;
bool p[maxn]={0};
void Find_Prime(){
for(int i=2;i<maxn;i++){
if(p[i]==false){
prime[num++]=i;
for(int j=i+i;j<maxn;j=j+i){
p[j]=true;
}
}
}
}
struct factor{
int cnt,x;
}fac[10];
int main()
{
Find_Prime();
int n;
while(cin>>n){
int no=0;
int sqr=(int)sqrt(1.0*n);
//质因数一定是小于数的根号！！
for(int i=0;i<num&&prime[i]<=sqr;i++){
if(n%prime[i]==0){
fac[no].cnt=0;
fac[no].x=prime[i];
//重复除以当前质数，计算该质数的数量
while(n%prime[i]==0){
fac[no].cnt++;
n=n/prime[i];
}
no++;
}
if(n==1) break;
}
//次数的意思是n不为1，且n是质数时，自己是自己的质因数
if(n!=1){
fac[no].x=n;
fac[no].cnt=1;
no++;
}
int count=0;
for(int i=0;i<no;i++)
//次数如果是求约数的话！！要用乘以所有质因数的办法
// count*=(fac[i].cnt+1);
count=count+fac[i].cnt;
cout<<count<<endl;
}
return 0;
}
方法二：太强了！！，这个逻辑
#include <iostream>
using namespace std;
int main()
{
long m;
while(cin>>m){
long cnt=0;
for(long j=2;j*j<=m;j++){
while(m%j==0){
m=m/j;
cnt++;
}
}
//这个意思是质数本身么
if(m>1) cnt++;
cout<<cnt<<endl;
}
return 0;
}
奇数魔方图
//C程序设计第五版（谭浩强）
//章节：第六章 利用数组处理批量数据
//题号：6.7
//题目：输出奇数阶魔方阵
// 将1放在第一行中间一列;
// 从2开始直到 n×n为止各数依次按照如下规则存放
// 1）每一个数存放的行是前一个数的行减去1，列数加1(例如三阶魔方阵，5在4的上一行后一列);
// 2）如果前一个数的行数为1，那么下一个数的行数为n（最后一行），列同样，如果前一个数的列数为n，那么下一个数的列数为1；
// 3）如果按照上面规则存放时发现位置上已存在数或者上一个数是第一行第n列时，则把下一个数放在上一个数的下面即可。
#include <stdio.h>
int main(){
int x[100][100]={0},i,j,n,a,b;
printf("您打算输出几阶魔方阵（奇数阶）：");
scanf("%d", &n);
a = 0;
b = n/2;
x[a][b] = 1; // 1
for(i=2;i<=n*n;i++){
//特殊情况都输出也不错
if(a==0 && b!=n-1){ // 前一个数在第一行但是不在最后一列
a = n-1;
b = b+1;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数,则把这个数放在上一个数的下方
a = 1;
b = b-1;
x[a][b] = i;
}
}
else if(a!=0 && b==n-1){ // 前一个数不在第一行但是在最后一列
a = a-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = a+1;
b = n-1;
x[a][b] = i;
}
}
else if(a==0 && b==n-1){ // 前一个数在第一行同时在最后一列
a = n-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = 1;
b = n-1;
x[a][b] = i;
}
}
else{
a = a-1;
b = b+1;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
//终于看懂了！！不变的意思，自己对自己操作！！
a = a+2;
b = b-1;
x[a][b] = i;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%5d", x[i][j]);
}
printf("\n");
}
return 0;
}
//优化版！！，主要是总结归纳特殊情况为a = (a-1+3)%3;b = (b+1+3)%3;
int main(){
int x[100][100]={0},i,j,n,a,b;
printf("您打算输出几阶魔方阵（奇数阶）：");
scanf("%d", &n);
a = 0;
b = n/2;
x[a][b] = 1; // 1
for(i=2;i<=n*n;i++){
//特殊情况都输出也不错,特殊情况应当优先判断！！！
if(a==0 && b==n-1){ // 前一个数在第一行同时在最后一列
a = n-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = 1;
b = n-1;
x[a][b] = i;
}
}
else{
a = (a-1+3)%3;
b = (b+1+3)%3;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
//终于看懂了！！不变的意思，自己对自己操作！！
a = a+2;
b = b-1;
x[a][b] = i;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%5d", x[i][j]);
}
printf("\n");
}
return 0;
}
求小数的循环部分，模除法
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
/*
①11<13,11*10/13=8,余数=6
②6<13,6*10/13=4,余数=8
③8<13,8*10/13=6,余数=2
④2<13,2*10/13=1,余数=7
⑤7<13,7*10/13=5,余数=5
⑥5<13,5*10/13=3,余数=11
⑦11<13,11*10/13=8,余数=6
都是用余数乘以10去除以的，最终商和余数都相等，则有循环节
分成两部分：
第一部分模拟除法运算，每进行一步除法运算，
都需要将得到的商和余数分别保存在数组中，商用来输出，余数用来
判断是否循环，要在第二部分当中检测。
第二部分：将传递进来的商和余数，和保存在数组中的历史商和余数进行比较
若不相等，第一部分继续运算，若相等，记下当前商的所在下标
下标即为循环节的起始位置
*/
//第二部分的判断
int pos=0;
bool findR(vector<int> rem, vector<int> dec, int r, int c)
{
for (int i = 0; i < dec.size(); i++)
{
if (rem[i] == r && dec[i] == c)
{
pos = i;
return false;
}
}
return true;
}
void dipose(int n, int d)
{
string fp = to_string(n / d) + "."; //整数部分
if (n > d) //第一次除法
{
n = n % d;
}
int r, c; //r是余数，c是商
c = n * 10 / d;
r = (n * 10) % d;
vector<int> rem, dec; //rem是商数组保存之前的商，dec是余数数组保存之前的余数
bool flag = true;
while (findR(rem, dec, r, c))
{
dec.push_back(c);
rem.push_back(r);
r *= 10;
c = r / d;
r %= d;
if (c == 0)
{
flag = false; //flag为true为循环小数，flag为false为不循环小数
break;
}
}
cout << fp;
for (int i = 0; i < pos; i++)
{
cout << dec[i];
}
for (int i = pos; i < dec.size(); i++)
{
if (i == pos && flag)
{
cout << "(";
}
cout << dec[i];
if (i == dec.size() - 1 && flag)
{
cout << ")";
}
}
cout << endl;
}
int main()
{
int a1,b1,a2,b2,a3,b3;
scanf("%d/%d %d/%d %d/%d",&a1,&b1,&a2,&b2,&a3,&b3);
dipose(a1,b1);
dipose(a2,b2);
dipose(a3,b3);
}
求最大公约数
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
求最小公约数
求得A和B的最大公约数是C，则最小公倍数A*B/C
矩阵排序思想
/*输入一个四行五列矩阵，找出每列对最大的两个数*/
/*
第二题：输入一个四行五列的矩阵，找出每列最大的两个数，如：
输入：
1 2 3 4 9
-1 4 9 8 8
12 9 8 7 0
7 8 9 7 0
输出：12 9 9 8 9
7 8 9 7 8*/
/*循环五次，每次对每一列进行快排(降序)，最后将前两行的结果输出即可*/
#include <iostream>
#include <algorithm>
using namespace std;
//bool型返回值
bool comp(int a,int b){
return a>b;
}
//好思想，先排序，排序好后再将原来的数字替换，输出前两行即可，关键是思想到位，知道怎样
//在矩阵当中对于列排序
int main(){
int buf[4][5];
int x;
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
cin>>x;
buf[i][j]=x;
}
}
int tmp[4];
for(int j=0;j<5;j++){
for(int i=0;i<4;i++){
//傻傻了，行列依然不变，i，j，这样就是(0,0)(1,0)(2,0)(3,0)
tmp[i]=buf[i][j];
//不用会表达一列，只需要把它们可以取出来，用中间数列进行排序
}
sort(tmp,tmp+4,comp);
for(int i=0;i<4;i++){
buf[i][j]=tmp[i];
}
}
for(int i=0;i<2;i++){
for(int j=0;j<5;j++){
cout<<buf[i][j]<<" ";
}
cout<<endl;
}
}
求约数节省效率办法
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//求约数的方法太落后了,没考虑时间复杂度
int yueshu(int x){
int cnt=0;
for(int i=1;i*i<=x;i++){
if(x==i*i)
cnt=cnt+1;
else if(x%i==0){
//仔细考虑一下确实是对称的！！
cnt=cnt+2;
}or
}
return cnt;
}
//这个方法也不错
int numOfDivisor(int num)
{
int ans = 0;
int i;
for (i = 1; i*i<num; i++)
{
if (num%i == 0)
ans += 2;
}
if (i*i == num) ans++;
return ans;
}
int main()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
int x;
cin>>x;
cout<<yueshu(x)<<endl;
}
}
return 0;
}
简单约瑟夫环
/*n个人排一圈123报数，报到3的人退到圈外，直到剩最后一个人为止。*/
//终于自我分析出了约瑟夫环
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin>>n){
int count=n;
int num=1;
//这样分配内存保险
int arr[1000];
for(int i=0;i<=n;i++){
arr[i]=1;
}
while(count!=1){
for(int i=1;i<=n;i++){
if(arr[i]==0) continue;
else{
if(num!=3){
num++;
}else{
cout<<i<<endl;
num=1;
arr[i]=0;
count--;
}
}
if(i==n) i=0;
}
}
for(int i=1;i<=n;i++){
if(arr[i]==1) cout<<i<<endl;
}
}
}
高级链表版约瑟夫环（单循环链表）
#include<stdio.h>
#include<stdlib.h>
typedef struct node{//链表结点数据结构定义；
int data;
struct node *next;
}LNode,*LinkList;
void Josephus(int n,int k,int m){//约瑟夫环问题；n：人数，k：开始计数位置，m：数到几退出一个人；
LinkList p,q,r;//p指向表头；
int i,cnt;
p=(LinkList)malloc(sizeof(LNode));
p->data=1;
p->next=NULL;
q=p;
for(i=2;i<=n;i++){//创建单循环链表；如何创建单循环链表
r=(LinkList)malloc(sizeof(LNode));
r->data=i;
r->next=NULL;
q->next=r;
q=q->next;
}
//此处指向队头，完成连接
q->next=p;
//走到开始计数的位置
for(i=1;i<k;i++){
q=p;//q始终指向前驱；
p=p->next; //p移到开始的结点；
}
cnt=1;
//也就是说只剩最后一个结点时，自己指向自己
while(q->next!=q){
cnt++;
q=p;
p=p->next;
if(cnt%m==0){//将要退出一个人；
printf("%d ",p->data);
q->next=p->next;
p=p->next;
cnt++;
}
}
printf("%d/n",q->data);
}
int main(){
int n,k;
printf("请输入人数n、从谁开始数k:\n");
scanf("%d %d",&n,&k);
Josephus(n,k,3);
system("pause");
}
约瑟夫环再进阶版，拆封成.h和.c多个文件
/*
生成一个长度为21的数组，依次存入1到21；建立一个长度为21的单向链表，将上述数组中的数字依次存入链表每个结点中；将上述链表变为单向封闭(循环)链表；从头结点开始数，将第17个结点删除，将它的下一个结点作为新的头结点；重复上述过程，直到该链表中只剩一个结点，显示该结点中存入的数字。
分三个文件，一个main; 一个.h; 一个.c 文件。
*/
count21.h文件：
#ifndef COUNT_21_H_INCLUDED
#define COUNT_21_H_INCLUDED
#define NUM 21//链表节点数；
typedef struct node{//链表结点数据结构定义；
int data;
struct node *next;
}LNode,*LinkList;
LinkList CreateList();//创建单循环链表；
#endif
count21.c文件：
#include<stdio.h>
#include<stdlib.h>
#include"Count21.h"
LinkList CreateList(){//建立单循环链表；
LinkList L,p,q;
int i;
L=(LinkList)malloc(sizeof(LNode));
p=L;
L->data=1;
L->next=NULL;
for(i=2;i<=NUM;i++){
q=(LinkList)malloc(sizeof(LNode));
q->data=i;
q->next=NULL;
p->next=q;
p=p->next;
}
p->next=L;//构成循环链表；
return L;
}
main.c文件
#include<stdio.h>
#include<stdlib.h>
#include"Count21.h"
int main(){
LinkList L,p,q;
L=CreateList();
p=L;//p指向当前节点；
q=L;
while(q->next!=L){
q=q->next;
}//q指向前驱；
int cnt=1;
while(q->next!=q){
cnt++;
q=p;
p=p->next;
if(cnt%17==0){
printf("%d ",p->data);
q->next=p->next;
p=p->next;
cnt++;
}
}
printf("%d/n",p->data);
system("pause");
}
