算法競賽入門【碼蹄集新手村600題】(MT1351-1400）
(文章目錄)
前言
為什麼突然想學算法了？
> 用較為“官方”的語言講，是因為算法對計算機科學的所有分支都非常重要。 在絕大多數的計算機科學分支領域中，要想完成任何實質性的工作，了解算法的基礎知識并掌握與算法密切相關的資料結構知識是必不可少的。
> 但從實際而言，是因為當下快到了考研和找工作的年紀(ಥ_ಥ)，無論走哪一條路，都不免需要一些相對豐富的算法知識，是故，便産生了一個暑假速成算法的計劃，可能對于像我這種算法競賽小白而言，幾乎很難，但我仍然還是想嘗試一下，畢竟，夢想還是要有的，萬一實作了呢？～(￣▽￣～)~
為什麼選擇碼蹄集作為刷題軟體？
碼蹄集，是在全國高等學校計算機教學與産業實踐資源建設專家委員會(TIPCC) 指導下建設的，其依托全國各大名校計算機系和清華大學出版社等機關的強大資源，旨在為計算機學習愛好者提供全面和權威的計算機習題。
算法競賽入門【碼蹄集新手村600題】(MT1351-1400）算法競賽入門【碼蹄集新手村600題】(MT1351-1400）前言目錄
目錄
1. MT1351 用函數判斷素數
（1）題目描述
編寫函數fun判斷素數，主函數中輸入正整數n，輸出判斷結果。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出Y或者N
樣例1
輸入格式: 5
.
輸出格式: Y
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool is_Prime(int n){
bool flag=true;
if(n==1) flag=false;
else if(n==2) flag=true;
else if(n%2==0) flag=false;
for(int i=3;i<=n/2;i=i+2){
if(n%i==0) flag=false;
}
return flag;
}
int main( )
{
int n;
cin>>n;
if(is_Prime(n)) cout<<"Y";
else cout<<"N";
return 0;
}
2. MT1352 埃拉托色尼篩選法
（1）題目描述
輸入正整數N(<10000)，編寫一個函數，用埃拉托色尼篩選法輸出N以下的素數(含N)。
格式
輸入格式: 輸入正整數N
.
輸出格式:輸出整型，空格分隔。
樣例1
輸入格式: 35
.
輸出格式: 2 3 5 7 11 13 17 19 23 29 31
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool is_Prime(int n){
bool flag=true;
if(n==1) flag=false;
else if(n==2) flag=true;
else if(n%2==0) flag=false;
for(int i=3;i<=n/2;i=i+2){
if(n%i==0) flag=false;
}
return flag;
}
int main( )
{
int n;
cin>>n;
for(int i=2;i<=n;i++){
if(is_Prime(i)) cout<<i<<" ";
}
return 0;
}
3. MT1353 找零
（1）題目描述
人民币面值有1、2、5、10、20、50元。編寫函數change(m,c);其中m為商品價格，c為顧客付款。函數輸出應給顧客找零的各種面值人民币的總張數，且總數之和最少。
不考慮負數或者其他非法輸入等特殊情況。
格式
輸入格式: 輸入商品價格，顧客付款，均為整型，機關為元，空格分隔。
.
輸出格式: 輸出為整型
樣例1
輸入格式: 7 10
.
輸出格式: 2
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int m,c;
cin>>m>>c;
int p=c-m;
int n=0;
while(p>0){
if(p>=50) p-=50;
else if(p>=20) p-=20;
else if(p>=10) p-=10;
else if(p>=5) p-=5;
else if(p>=2) p-=2;
else p--;
n++;
}
cout<<n;
return 0;
}
4. MT1354 購物
（1）題目描述
人民币面值有:1、2、5分，1、2、5角，1、2、5、10、20、50元。編寫函數change(m,c);其中m為商品價格，c為顧客付款。函數輸出應給顧客找零的各種面值人民币的總張數，且總數之和最少。
不考慮負數或者其他非法輸入等特殊情況。
格式
輸入格式: 輸入商品價格，顧客付款，均為實型，機關為元，空格分隔。
.
輸出格式: 輸出為整型
樣例1
輸入格式: 7 10
.
輸出格式: 2
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int change(int m,int c){
int remain=c-m;
int sum=0;
int a[]={1,2,5,10,20,50,100,200,500,1000,2000,5000};
for(int i=11;i>=0;i--){
int cnt=remain/a[i];
sum+=cnt;
remain -= cnt*a[i];
}
return sum;
}
int main( )
{
double m,c;
int ma,ca;
scanf("%lf %lf",&m,&c);
ma=m*100,ca=c*100;
printf("%d",change(ma, ca));
return 0;
}
5. MT1355 稀疏二進制
（1）題目描述
輸入正整數N，編寫函數判斷它的二進制形式是不是一個稀疏二進制，是就輸出，如果不是就查找其下一個數，直到找到稀疏二進制數并輸出。稀疏二進制數是二進制表示形式不包含任何連續1的數。
格式
輸入格式: 輸入正整數N
.
輸出格式:輸出整型
樣例1
輸入格式: 3
.
輸出格式: 4
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
bool getSparseBinary(int x){
int temp=0;
bool flag = false;
while(x){
temp=x%2;
if(temp==1&&!flag) flag=true;
else if(temp==0) flag=false;
else return false;
x/=2;
}
return true;
}
int main( )
{
int n;
cin>>n;
while(1){
if(getSparseBinary(n)){
cout<<n<<endl;
break;
}
n++;
}
return 0;
}
6. MT1356 二進制回文
（1）題目描述
輸入正整數N，編寫一個函數，判斷它的二進制表示形式是否為回文輸出YES或者NO。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 17
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
string s;
cin>>n;
while(n){
s+=n%2;
n/=2;
}
int len = s.size();
for(int i=0,j=len-1;i<j;i++,j--){
if(s[i]!=s[j]){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
return 0;
}
7. MT1357 高低變換
（1）題目描述
編寫函數，計算将unsigned char型n的二進制表示形式的低四位和高四位交換後的結果。在主函數中輸入資料調用函數輸出結果。
格式
輸入格式: 輸入為字元型
.
輸出格式: 輸出為字元型
樣例1
輸入格式: T
.
輸出格式: E
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
unsigned char change(unsigned char c){
return (c>>4) | (c<<4);
}
int main( )
{
unsigned char ch;
cin>>ch;
cout<<change(ch)<<endl;
return 0;
}
8. MT1358 第k位
（1）題目描述
編寫函數int getbit(int n,int k);求出n的二進制表示形式的從右邊開始的第k位(從1開始計數)。在主函數中輸入資料并調用該函數輸出結果。
格式
輸入格式: 輸入n, k為正整數，空格分隔。
.
輸出格式: 輸出位整型
樣例1
輸入格式: 1 3
.
輸出格式: 0
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[10000],cnt=0;
int getbit(int n,int k){
while(n){
dp[++cnt] = n%2;
n/=2;
}
return dp[cnt-k+1];
}
int main( )
{
int n,m;
cin>>n>>m;
cout<<getbit(n,m)<<endl;
return 0;
}
9. MT1359 循環移位
（1）題目描述
編寫函數實作左右循環移位。函數原型為unsigned move(unsigned value,intn);其中value為要循環移位的數，n為移位的位數。如果n<0表示左移，n>0表示右移，n=O表示不移位。在主函數中輸入資料并調用該函數得到結果并在主函數輸出。(在4位2進制表示中進行位移，且0<value<15)
格式
輸入格式: 輸入value, n為整型，空格分隔。
.
輸出格式: 輸出為整型
樣例1
輸入格式: 9 1
.
輸出格式: 12
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int v,n,t;
bool f=false;
cin>>v>>n;
if(n==0) cout<<v;
else{
if(n>0) f=true;
if(f){
while(n--){
t=v&1;
v=v>>1;
v+=t<<3;
}
}else{
n=-n;
while(n--){
t=v&8;
t=t>>3;
v=v<<1;
v=v&15;
v+=t;
}
}
cout<<v;
}
return 0;
}
10. MT1360 左右函數
（1）題目描述
輸入一個字元串(至少3個字元)，編寫2個函數，函數名分别為left,right，他們分别複制字元串最左邊或者最右邊3個字元到新數組中并輸出。
格式
輸入格式: 輸入字元串
.
輸出格式: 第一行輸出最左邊3個字元，第二行輸出最右邊3個字元。
樣例1
輸入格式: Coding is fun
.
輸出格式:
Cod
fun
（2）參考代碼
import java.util.Scanner;
import java.util.*;
class Main {
private static String left(String s){
return s.substring(0,3);
}
private static String right(String s){
return s.substring(s.length()-3);
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
String s = sc.nextLine();
System.out.println(left(s));
System.out.println(right(s));
sc.close();
}
}
11. MT1361 重組字元串
（1）題目描述
編寫一個函數，保留字元串中下标為奇數同時ASCII碼值也為奇數的字元，其餘全部删除，把它們存放到一個新串并傳回給主調函數，在主調函數中輸出。
格式
輸入格式: 輸入字元串
.
輸出格式: 輸出字元串
樣例1
輸入格式: 0123456789
.
輸出格式: 13579
（2）參考代碼
import java.util.Scanner;
import java.util.*;
class Main {
public static String newString(String n){
String s = "";
for(int i=0;i<n.length();i++){
if(i%2 != 0&&(n.charAt(i) + 48)%2!=0) s+=n.charAt(i);
}
return s;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// code here
System.out.println(newString(input.next()));
input.close();
}
}
12. MT1362 特殊排序
（1）題目描述
輸入字元串，編寫2個排序函數，把字元串左半邊按ASCIl值降序排序，右半邊升序排序，再左右兩邊進行交換。如果有奇數個字元，中間一個不動。輸出交換後的字元串。
格式
輸入格式: 輸入字元串
.
輸出格式: 輸出字元串
樣例1
輸入格式: abcd9876
.
輸出格式: 6789dcba
（2）參考代碼
import java.util.Scanner;
import java.util.*;
class Main {
static String ascAscII(String o){
char[] tmp = o.toCharArray();
Arrays.sort(tmp);
return new String(tmp);
}
static String descAscII(String o){
char[] tmp=o.toCharArray();
Arrays.sort(tmp);
return new StringBuilder(new String(tmp)).reverse().toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String n = sc.next();
StringBuilder sb = new StringBuilder();
if(n.length()%2!=0){
sb.append(ascAscII(n.substring(n.length()/2+1)));
sb.append(n.charAt(n.length()/2));
sb.append(descAscII(n.substring(0,n.length()/2)));
}else{
sb.append(ascAscII(n.substring(n.length()/2)));
sb.append(descAscII(n.substring(0,n.length()/2)));
}
System.out.println(sb);
sc.close();
}
}
13. MT1363 孿生質數
（1）題目描述
設計一個函數，将字元串"ABBDDDFFF"的字元串的前導*、中間*、末尾*删除。
格式
輸入格式: 無
.
輸出格式: 輸出字元串
樣例1
輸入格式: 無
.
輸出格式: ABBDDDFFF
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
void del(char s[]){
int len=strlen(s);
for(int i=0;i<len;i++){
if(s[i]=='*'){
for(int j=i;j<len;j++){
s[j]=s[j+1];
}
len--;
i--;
}
}
}
int main( )
{
char s[]="****ABB*DDDFFF***";
del(s);
printf("%s",s);
return 0;
}
小結(一)
經典範例：
MT1352：埃拉托色尼篩選法 (the Sieve of Eratosthenes)簡稱埃氏篩法，是古希臘數學家埃拉托色尼 (Eratosthenes 274B.C.～194B.C.)提出的一種篩選法。 是針對自然數列中的自然數而實施的，用于求一定範圍内的質數，它的容斥原理之完備性條件是p=H~。
要得到自然數n以内的全部素數，必須把不大于 的所有素數的倍數剔除，剩下的就是素數。 [1]
給出要篩數值的範圍n，找出以内的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。算法代碼
找零： MT1353、MT1354
二進制系列： MT1355-1358
字元串系列： MT1359-1363
14. MT1364 遞歸求工資
（1）題目描述
有5個人坐在一起，問第5個人多少工資，他說比第4個人多200。問第4個人多少工資，他說比第3個人多200，問第3人，他說比第2個人多200。問第2個人，他說比第1個人多200。最後問第1個人，他說他是1000塊錢。編寫程式，當輸入第幾個人時求出其對應的工資。
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 1800
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
cin>>n;
int a[]={1000,1200,1400,1600,1800};
cout<<a[n-1];
return 0;
}
15. MT1365 分桃
（1）題目描述
用遞歸法求解:猴子第一天摘下若幹個桃子，當即吃了一半，又多吃了一個;第二天早上又将剩下的桃子吃掉一半，又多吃了一個。以後每天早上都吃了前一天剩下的一半零一個。到第10天早上時，隻剩下一個桃子。問第一天至少摘了多少個桃子?
格式
輸入格式: 無
.
輸出格式: 輸出為整型
樣例1
輸入格式: 無
.
輸出格式: 1534
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int fun(int day){
if(day==10) return 1;
else return 2*fun(day+1)+2;
}
int main( )
{
cout<<fun(1);
return 0;
}
16. MT1366 用函數求平方和
（1）題目描述
編寫函數fun,求11+22+33+.....+nn的和。主函數中輸入正整數n，輸出累加和
格式
輸入格式: 輸入整型
.
輸出格式: 輸出整型
樣例1
輸入格式: 3
.
輸出格式: 14
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int fun(int n){
int sum=0;
for(int i=1;i<=n;i++){
sum+=i*i;
}
return sum;
}
int main( )
{
int n;
cin>>n;
cout<<fun(n);
return 0;
}
17. MT1367 求解函數
（1）題目描述
已知ack函數對于m≥0和n≥0有定義: ack(0,n)=n+1、ack(m,0)=ack(m-1,1).ack(m,n)=ack(m-1,ack(m,n-1))。
輸入m和n，求解ack函數。(本題中m和n不同時為0)
格式
輸入格式: 輸入為正整數，空格分隔
.
輸出格式: 輸出為整型
樣例1
輸入格式: 3 5
.
輸出格式: 253
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int ack(int m,int n){
if(m==0) return n+1;
else if(n==0) return ack(m-1,1);
else return ack(m-1,ack(m,n-1));
}
int main( )
{
int m,n;
cin>>m>>n;
cout<<ack(m,n)<<endl;
return 0;
}
18. MT1368 遞歸法求逆序
（1）題目描述
用遞歸法求解:将一個四位數(如5678)逆序(如8765)。不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入大于0的4位正整數
.
輸出格式: 輸出為整型
樣例1
輸入格式: 1234
.
輸出格式: 4321
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
void f(int n){
if(n==0) return;
else{
cout<<n%10;
f(n/10);
}
}
int main( )
{
int n;
cin>>n;
f(n);
return 0;
}
19. MT1369 楊輝三角
（1）題目描述
編寫函數輸出楊輝三角形
格式
輸入格式: 輸入為正整數
.
輸出格式: 輸出為整型
樣例1
輸入格式: 3
.
輸出格式:
1
1 1
1 2 1
（2）參考代碼
#include <iostream>
using namespace std;
int num[25][25]={1}; //num[0][0]=1
int main(int argc, char const *argv[])
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
num[i][j]=num[i-1][j]+num[i-1][j-1];//第i行第j列的值等于第i-1行第j列與第i-1行第j-1列的和
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cout<<num[i][j];
if(j<i){
cout<<" ";
}
}
cout<<endl;
}
return 0;
}
20. MT1370 遞歸函數
（1）題目描述
輸入正整數N，遞歸地對N的位數求和，直到得到一個位數并輸出。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 1234
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int f(int n){
int ans=0;
if(n/10==0) return n;
else{
while(n){
ans+=n%10;
n/=10;
}
return f(ans);
}
}
int main( )
{
int n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}
21. MT1371 所有路徑
（1）題目描述
輸入整型M和N(均大于2小于100)，用遞歸函數計算MxN矩陣從左上角到右下角的所有可能路徑(每一步路徑隻能往下、往右走)。
格式
輸入格式: 輸入整型M和N，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式:3 3
.
輸出格式: 6
備注：
結果可能比較大，建議用長整型
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
long int getPath(long mem[][],int x,int y){
if(mem[x][y]!=0) return mem[x][y];
if(x==0&&y!=0){
mem[x][y] = getPath(mem, x, y-1);
return mem[x][y];
}
if(x!=0&&y==0){
mem[x][y]=getPath(mem, x-1, y);
return mem[x][y];
}
mem[x][y] = getPath(mem, x-1, y)+getPath(mem, x, y-1);
return mem[x][y];
}
int main( )
{
int m,n;
cin>>m>>n;
long int mem[m][n];
mem[0][1]=1;
mem[1][0]=1;
getPath(mem, m-1, n-1);
return 0;
}
小結(二)
經典例題
ACK函數：MT1367
遞歸法逆序：MT1368
楊輝三角：MT1369
遞歸求和：MT1370
所有路徑：MT1371
22. MT1372 矩陣清零
（1）題目描述
設計一個函數，将NXN的矩陣所有元素替換成0。
格式
輸入格式: 第一行輸入N (<100)，第二行輸入數組元素，整型，空格分隔。
.
輸出格式: 輸出整型矩陣，空格分隔。
樣例1
輸入格式:
3
1 2 3 4 5 6 7 8 9
.
輸出格式:
0 0 0
0 0 0
0 0 0
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[105];
cin>>n;
for(int i=0;i<n*n;i++) cin>>a[i];
for(int i=0;i<n;i++){
for(int i=0;i<n;i++) cout<<0<<" ";
cout<<endl;
}
return 0;
}
23. MT1373 親和數
（1）題目描述
A所有的真約數（除自身之外的約數)之和為B，而B所有的真約數之和為A，這樣的兩個正整數就是親和數。
輸入兩個正整數，編寫一個函數判斷他們是不是親和數，輸出YES或者NO。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出YES或者NO
樣例1
輸入格式: 220 284
.
輸出格式: YES
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int getSum(int a){
int sum=0;
for(int i=1;i<a;i++){
if(a%i==0){
sum+=i;
}
}
return sum;
}
int main( )
{
int m,n;
cin>>m>>n;
if(getSum(m)==n&&getSum(n)==m) cout<<"YES";
else cout<<"NO";
return 0;
}
24. MT1374 Pronic數
（1）題目描述
請編寫一個函數求m至n之間的所有Pronic數字，如果某個數字是兩個連續數字的乘積,則該數字被稱為Pronic數。比如6 = 2 x 3，72 = 8 x 9。
輸入整數區間，輸出區間(含邊界）内所有的Pronic數。在主函數中輸入m和n，調用函數int PronicNumber(int x)進行判斷，再在主函數中輸出結果。
不考慮不合理的輸入或是溢出等特殊情況。
格式
輸入格式: 輸入為正整數，空格分隔
.
輸出格式: 輸出為整型，空格分隔
樣例1
輸入格式: 1 100
.
輸出格式: 2 6 12 20 30 42 56 72 90
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int is_Pronic(int x){
int i=1;
while(1){
ll temp=0;
temp=i*(i+1);
if(temp<x){
i++;
continue;
}
else if(temp==x) return 1;
else return 0;
}
}
int main( )
{
int n,m;
cin>>n>>m;
for(int i=n;i<=m;i++){
if(is_Pronic(i)) cout<<i<<" ";
}
cout<<endl;
return 0;
}
25. MT1375 4和7的序列
（1）題目描述
有一個由數字4和7組成的序列，如4，7，44,47，74...44744...等。輸入正整數N，編寫一個函數，輸出第N個數字。
格式
輸入格式: 輸入正整數N
.
輸出格式: 輸出整型
樣例1
輸入格式: 5
.
輸出格式: 74
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
string s;
int len,dp[1000],cnt=0;
bool flag=false;
void getFourAndSevent(){
for(int i=4;i<=1000000;i++){
s=to_string(i);
len = s.size();
flag = true;
for(int j=0;j<len;j++){
if(s[j]!='4'&&s[j]!='7'){
flag=false;
break;
}
}
if(flag) dp[++cnt]=i;
}
}
int main( )
{
int n;
cin>>n;
getFourAndSevent();
cout<<dp[n]<<endl;
return 0;
}
26. MT1376 小碼哥的數學
（1）題目描述
小碼哥會做100以内的加法，遇到大于等于100的數，小碼哥會“聰明”地用最後兩位計算，如果計算結果大于等于100，小碼哥也隻識别最後兩位。是以，小碼哥認為，134和34是一樣的。99+35是等于34的。
輸入N組資料，編寫函數做加法計算。
不考慮負數等特殊情況。
格式
輸入格式: 第一行輸入正整數N，後面N行輸入資料，空格分隔。
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
2
35 99
15 1152
.
輸出格式:
34
67
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int doubi(int n,int m){
n=n+m;
n=n%100;
return n;
}
int main( )
{
int n,a,b;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d %d",&a,&b);
cout<<doubi(a, b)<<endl;
}
return 0;
}
27. MT1377 模乘逆元
（1）題目描述
給定兩個正整數a和m。編寫一個函數，找到模’ m'下' a’的最小模乘逆元b。模乘逆元定義:滿足a * b=1 (mod m)，稱b為a模乘逆元 (b<m)。
注: x=n(mod m)意思是x除以m的餘數是n。
格式
輸入格式: 輸入正整數a和m，空格分隔。
.
輸出格式: 輸出整型
樣例1
輸入格式: 3 11
.
輸出格式: 4
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int getInverse(int a,int m){
int b=1;
while(b<=m){
if((a*b)%m==1) return b;
b++;
}
return -1;
}
int main( )
{
int a,m;
cin>>a>>m;
cout<<getInverse(a,m)<<endl;
return 0;
}
28. MT1378 一堆花甲
（1）題目描述
用函數求解:有5隻海豚在海邊發現一堆花甲，決定第二天來平分。第二天清晨，第一隻海豚最早來到，朝海裡扔了一隻後，恰好可以分成5份，它拿上自己的一份走了。第2，3，4，5隻海豚采用了同樣的方法，都是扔掉一隻後，恰好可以分成5份，然後拿上自己的一份走了。問這堆花甲至少有多少隻。
格式
輸入格式: 無
.
輸出格式: 輸出整型
樣例1
輸入格式: 無
.
輸出格式: 3121
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int pass(int n){
if((n-1)%5!=0) return 0;
return (n-1)/5*4;
}
int main( )
{
int number=1;
bool found=false;
while(!found){
int tmp=number;
for(int i=0;i<5;i++){
tmp=pass(tmp);
if(tmp==0) break;
}
if(tmp!=0){
cout<<number;
found=true;
}
number++;
}
return 0;
}
29. MT1379 operate函數
（1）題目描述
編寫函數operate(int a,int b,char op)。每次調用operate函數時可以實作不同的功能，如計算a和b的和、差。
格式
輸入格式: 輸入a，op , b，其中a、b為整型，op為+或者-。
.
輸出格式: 輸出整型
樣例1
輸入格式: 3+5
.
輸出格式: 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int operate(int a,int b,char op){
if(op=='+') return a+b;
else if(op=='-') return a-b;
}
int main( )
{
int a,b;
char op;
cin>>a>>op>>b;
cout<<operate(a, b, op);
return 0;
}
30. MT1380 mymath函數
（1）題目描述
編寫函數mymath(int a,int b,char op)。每次調用mymath函數時可以實作不同的功能，如a和b的乘、除、求餘計算。不考慮不合理的輸入等特殊情況。
格式
輸入格式: 輸入a，op , b，其中a、b為整型，op為*，/或者%。
.
輸出格式: 除法輸出實型，乘法和求餘輸出整型
樣例1
輸入格式: 3/5
.
輸出格式: 0.600000
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
void mymath(int a,int b,char op){
if(op=='*') printf("%d",a*b);
else if(op=='/') printf("%lf",(double)a/(double)b);
else if(op=='%') printf("%d",a%b);
}
int main( )
{
double a,b;
char op;
cin>>a>>op>>b;
mymath(a, b, op);
return 0;
}
31. MT1381 逆序輸出數組
（1）題目描述
定義一個長度為10的整型數組，輸入10個數組元素的值，然後逆序輸出他們
格式
輸入格式: 輸入10個數組元素的值，整型，空格分隔
.
輸出格式: 逆序輸出10個數組元素的值，整型，空格分隔
樣例1
輸入格式: 1 2 3 4 5 6 7 8 9 10
.
輸出格式: 10 9 8 7 6 5 4 3 2 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[11];
for(int i=0;i<10;i++) cin>>a[i];
for(int i=9;i>=0;i--) cout<<a[i]<<" ";
return 0;
}
32. MT1382 奇數項
（1）題目描述
定義一個長度為10的整型數組，輸入10個數組元素的值，然後輸出奇數項。
格式
輸入格式: 輸入10個數組元素的值，整型，空格分隔
.
輸出格式: 輸出數組奇數項，整型，空格分隔
樣例1
輸入格式: 1 2 3 4 5 6 7 8 9 10
.
輸出格式: 2 4 6 8 10
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[11];
for(int i=0;i<10;i++) cin>>a[i];
for(int i=1;i<=9;i=i+2) cout<<a[i]<<" ";
return 0;
}
33. MT1383 偶數項和偶數值
（1）題目描述
定義一個長度為10的整型數組，輸入10個數組元素的值，如果某一項既是偶數項又是偶數值，輸出他。
格式
輸入格式: 輸入10個數組元素的值，整型，空格分隔
.
輸出格式: 輸出符合要求的項，整型，空格分隔
樣例1
輸入格式: 1 2 4 0 5 6 8 7 9 10
.
輸出格式: 4 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[11];
for(int i=0;i<10;i++) cin>>a[i];
for(int i=0;i<=9;i=i+2) if(a[i]%2==0) cout<<a[i]<<" ";
return 0;
}
34. MT1384 李代桃僵
（1）題目描述
定義一個長度為10的整型數組，輸入10個數組元素的值，然後輸入要查找的數n，如果找到，把他替換成m
格式
輸入格式: 輸入整型,分2行輸入。第一行輸入10個數組元素的值，空格分隔，第二行輸入n和m，空格分隔
.
輸出格式: 輸出替換後的數組元素的值，空格分隔，整型
樣例1
輸入格式:
1 2 4 0 5 6 8 4 9 10
4 6
.
輸出格式: 1 2 6 0 5 6 8 6 9 10
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[11];
for(int i=0;i<10;i++) cin>>a[i];
int n,m;
cin>>n>>m;
for(int i=0;i<10;i++){
if(a[i]==n) a[i]=m;
}
for(int i=0;i<10;i++) cout<<a[i]<<" ";
return 0;
}
35. MT1385 查找
（1）題目描述
在一組給定的資料中，找出某個資料是否存在。定義長度為10的數組，輸入數組元素，和要查找的資料，如果找到輸出下标。沒找到則輸出No。
格式
輸入格式:
第1行輸入數組元素，空格分隔
第2行輸入要查找的整數n
.
輸出格式:輸出整型
樣例1
輸入格式:
1 2 3 4 5 6 7 8 9 10
2
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[11];
for(int i=0;i<10;i++) cin>>a[i];
int n;
cin>>n;
for(int i=0;i<10;i++){
if(a[i]==n){
cout<<i;
return 0;
}
}
cout<<"No";
return 0;
}
36. MT1386 第n個數
（1）題目描述
編寫程式讀入n (n<200）個整數(輸入-9999結束)。找出第1到第n -1個數中第1個與第n個數相等的那個數，并輸出該數的序号(序号從1開始）。如果沒有，則輸出”no such number"。
格式
輸入格式: 輸入為整型，空格分隔。
.
輸出格式: 輸出為整型
樣例1
輸入格式: 1 10 9 1 2 1 3 1 1 -9999
.
輸出格式: 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[10000];
int main( )
{
int n=1;
while(1){
scanf("%d",dp+n);
if(dp[n]==-9999) break;
n++;
}
for(int i=1;i<n-1;i++){
if(dp[i]==dp[n-1]){
cout<<i<<endl;
return 0;
}
}
cout<<"no such number"<<endl;
return 0;
}
37. MT1387 删除指定元素
（1）題目描述
定義一個長度為n的整型數組，輸入n個數組元素的值，然後輸入要删除的數編号，比如删掉從左向右第5個數，輸出删除後的數組。
格式
輸入格式: 輸入整型，分3行輸入。第一行輸入n，第二行輸入n個數組元素的值，空格分隔，第三行輸入編号
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
10
1 2 3 4 5 6 7 8 9 10
5
.
輸出格式: 1 2 3 4 6 7 8 9 10
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[1000];
int main( )
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++) cin>>dp[i];
cin>>m;
for(int i=1;i<=n;i++){
if(i==m) continue;
cout<<dp[i]<<" ";
}
cout<<endl;
return 0;
}
38. MT1388 指定元素II
（1）題目描述
定義一個長度為n的整型數組，輸入n個數組元素的值，然後輸入要删除的數，比如删掉5，輸出删除後的數組。沒有找到5就原樣輸出。
格式
輸入格式:輸入整型，分3行輸入。第一行輸入n，第二行輸入n個數組元素的值，空格分隔，第三行輸入要删除的數
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
10
1 2 3 4 5 6 7 8 9 10
5
.
輸出格式: 1 2 3 4 6 7 8 9 10
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[1000];
int main( )
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++) cin>>dp[i];
cin>>m;
for(int i=1;i<=n;i++){
if(dp[i]==m) continue;
cout<<dp[i]<<" ";
}
cout<<endl;
return 0;
}
39. MT1389 删除
（1）題目描述
輸入10個整型元素和一個整數N，對數組進行從小到大排序，再數組中查找N然後删除它，不改變原有的次序，輸出删除後的新數組，如果沒找到就原樣輸出。
若新數組沒有元素，輸出-1。
格式
輸入格式: 第一行輸入整型數組元素，空格分隔，第二行輸入N。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式:
9 8 5 0 4 2 1 5 7 3
1
.
輸出格式: 0 2 3 4 5 5 7 8 9
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[1000];
int main( )
{
bool flag=true;
int m;
for(int i=1;i<=10;i++) cin>>dp[i];
sort(dp+1,dp+11);
cin>>m;
for(int i=1;i<=10;i++){
if(dp[i]==m) continue;
flag=false;
cout<<dp[i]<<" ";
}
if(flag) cout<<-1;
cout<<endl;
cout<<endl;
return 0;
}
40. MT1390 查重
（1）題目描述
定義一個長度為n的整型數組，輸入n個數組元素的值，然後删除重複的數，輸出删除後的數組
格式
輸入格式: 定義一輸入整型，分2行輸入。第一行輸入n，第二行輸入n個數組元素的值，空格分隔
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
10
1 2 2 3 4 5 6 7 7 8
.
輸出格式:1 2 3 4 5 6 7 8
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int cnt,dp[1000],bucket[1000];
bool flag=true;
int del(int a[],int b[],int n){
cnt=0;
for(int i=1;i<=n;i++){
flag=false;
for(int j=1;j<=cnt;j++){
if(a[i]==b[j]){
flag=true;
break;
}
}
if(!flag) b[++cnt] = a[i];
}
return cnt;
}
int main( )
{
int n,ans;
cin>>n;
for(int i=1;i<=n;i++) cin>>dp[i];
ans=del(dp,bucket,n);
for(int i=1;i<=ans;i++) cout<<bucket[i]<<" ";
cout<<endl;
return 0;
}
小結(三)
典型範例：
親和數：MT1373
41. MT1391 連續元素
（1）題目描述
删除一個整型數組中的連續相同的元素。
格式
輸入格式: 第一行輸入數組元素個數N為整型，第二行輸入元素，如樣例所示。
.
輸出格式: 輸出為整型
樣例1
輸入格式:
9
1 1 1 1 2 1 3 1 1
.
輸出格式: 1 2 1 3 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[100],ans[100];
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int inserted=0;
for(int i=0;i<n;i++){
if(i==0 || ans[inserted-1] !=a[i]){
ans[inserted++] = a[i];
}
}
for(int i=0;i<inserted;i++) cout<<ans[i]<<" ";
return 0;
}
42. MT1392 保留一個
（1）題目描述
對整型數組排序，将有序數組中相同的元素僅僅保留一個。
格式
輸入格式: 第一行輸入數組元素個數N為整型，第二行輸入元素，如樣例所示。
.
輸出格式: 輸出為整型
樣例1
輸入格式:
9
1 1 1 1 2 1 3 1 1
.
輸出格式: 1 2 3
備注：
N不大于100
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[100],b[100],insert=0;
bool flag=true;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
flag=false;
for(int j=0;j<n;j++){
if(a[i]==b[j]){
flag=true;
break;
}
}
if(!flag) b[insert++]=a[i];
}
sort(b,b+insert);
for(int i=0;i<insert;i++) cout<<b[i]<<" ";
return 0;
}
43. MT1393 重複元素
（1）題目描述
請編寫一個簡單程式，輸入10個整型元素，依次輸出重複元素。
格式
輸入格式: 輸入整型元素，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式: 5 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[15],bucket[15];
int main( )
{
for(int i=1;i<=10;i++){
cin>>dp[i];
bucket[dp[i]]++;
}
for(int i=1;i<=10;i++){
if(bucket[dp[i]]>=2){
cout<<dp[i]<<" ";
bucket[dp[i]] = 0;
}
}
cout<<endl;
return 0;
}
44. MT1394 元素頻次
（1）題目描述
請編寫一個簡單程式，輸入10個整型元素，輸出數組中每個元素出現的次數。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 依次輸出元素頻次，每個一行。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式:
9 1
8 1
5 2
0 1
4 1
2 1
1 2
7 1
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[15],flag[15],cnt=0;
int main( )
{
for(int i=1;i<=10;i++){
cin>>dp[i];
}
for(int i=1;i<=10;i++){
if(flag[i]==1) continue;
cnt=1;
for(int j=i+1;j<=10;j++){
if(dp[i]==dp[j]){
cnt++;
flag[j]=1;
}
}
cout<<dp[i]<<" "<<cnt<<endl;
}
cout<<endl;
return 0;
}
45. MT1395 統計
（1）題目描述
統計一個整型數組中不同元素出現的次數。
格式
輸入格式: 第一行輸入數組元素個數N為整型，第二行輸入元素，如樣例所示。
.
輸出格式: 輸出為整型，前面是元素，後面是出現的次數，每種一行。
樣例1
輸入格式:
9
1 1 1 1 2 1 3 1 1
.
輸出格式:
1 7
2 1
3 1
備注：
N<500
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int dp[15],flag[15],cnt=0;
int main( )
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>dp[i];
}
for(int i=1;i<=n;i++){
if(flag[i]==1) continue;
cnt=1;
for(int j=i+1;j<=n;j++){
if(dp[i]==dp[j]){
cnt++;
flag[j]=1;
}
}
cout<<dp[i]<<" "<<cnt<<endl;
}
cout<<endl;
return 0;
}
46. MT1396 排序吧
（1）題目描述
定義一個長度為n的整型數組，輸入n個數組元素的值，然後輸出從小到大排序後數組元素。
格式
輸入格式: 輸入整型，分2行輸入。第一行輸入n，第二行輸入n個數組元素的值，空格分隔
.
輸出格式: 輸出整型，空格分隔
樣例1
輸入格式:
5
3 4 2 1 6
.
輸出格式: 1 2 3 4 6
備注：
N不大于100
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
47. MT1397 選擇排序
（1）題目描述
輸入10個整型元素，對數組進行選擇排序，輸出從小到大排序後的新數組。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式: 0 1 1 2 4 5 5 7 8 9
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[100];
for(int i=0;i<10;i++) cin>>a[i];
sort(a,a+10);
for(int i=0;i<10;i++) cout<<a[i]<<" ";
return 0;
}
48. MT1398 插入排序
（1）題目描述
輸入10個整型元素，對數組進行插入排序，輸出從小到大排序後的新數組。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式: 0 1 1 2 4 5 5 7 8 9
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[100];
for(int i=0;i<10;i++) cin>>a[i];
sort(a,a+10);
for(int i=0;i<10;i++) cout<<a[i]<<" ";
return 0;
}
49. MT1399 冒泡排序
（1）題目描述
輸入10個整型元素，對數組進行冒泡排序，輸出從小到大排序後的新數組。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式: 0 1 1 2 4 5 5 7 8 9
（2）參考代碼
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[100];
for(int i=0;i<10;i++) cin>>a[i];
sort(a,a+10);
for(int i=0;i<10;i++) cout<<a[i]<<" ";
return 0;
}
50. MT1400 快速排序
（1）題目描述
輸入10個整型元素，對數組進行快速排序，輸出從小到大排序後的新數組。
格式
輸入格式: 輸入整型，空格分隔。
.
輸出格式: 輸出整型，空格分隔。
樣例1
輸入格式: 9 8 5 0 4 2 1 5 7 1
.
輸出格式: 0 1 1 2 4 5 5 7 8 9
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int a[100];
for(int i=0;i<10;i++) cin>>a[i];
sort(a,a+10);
for(int i=0;i<10;i++) cout<<a[i]<<" ";
return 0;
}