HNUCM 2018级《算法分析与设计》练习三

Love The Way You Lie 2023-07-10 14:09 5阅读 0赞

# HNUCM 2018级《算法分析与设计》练习三 #

前言：  
递归拓展：全排列&整数划分

--------------------

## [A：狮子座学素数][A] ##

--------------------

**题意：**  
给定一数字n，判断1~n中，恰好有两个素因子的数的个数

**题解：**  
由于n<=3000，所以暴力可以过，对1~n中每个数枚举判断即可

--------------------

## [B：翻转字符串I][B_I] ##

--------------------

**题意：**  
给一个由多个单词组成的字符串，对每个单词逆序输出

**题解：**  
直接遍历一遍数组，然后遇到空格对前面的单词逆序输出即可，当然别忘记了最后一个单词

--------------------

## [C：变形词][C] ##

--------------------

**题意：**  
给定两个字符串，判断两个字符串中出现的字符种类和每个字符的数量是否相同  
是，输出：true，否，输出：false

**题解：**  
当然会C++，map肯定最香了。  
不会的话，也没关系，由于字符对应的ASCII码，最大也不过才127，于是我们开个130的数组即可，感觉这方法比map要更好

--------------------

## [D：矩阵中的点][D] ##

--------------------

**题意：**  
给定矩阵的四个顶点和需要判断的一个点，求点是否在矩形内

**题解：**  
如果不会计算几何和叉乘等相关知识的话，的确会有点难，之前写过一篇博客，那里有详讲：  
[判断点是否在矩形内][Link 1]

--------------------

## [E：超级青蛙][E] ##

--------------------

**题意：**  
青蛙可以一次跳一级，一次跳两级…一次跳n级，求青蛙跳n级有多少种方案

**题解：**  
f(n)=f(1)+f(2)+f(3)+…+f(n-1)+1  
f(n-1)=f(1)+f(2)+f(3)+…+f(n-2)+1

两者相合并得：  
**f(n)=2\*f(n-1)**

这样其实就可以做出来了，  
但是还可以继续推到一般式，而不用递推式

f(1)=1  
f(2)=2  
f(3)=4  
f(4)=8  
…

可以推出：  
**f(n)=2^(n-1)**

--------------------

## [F：字母全排列][F] ##

--------------------

**题意：**  
给定一个整数n，表示字符串的长度，其中字符串由a~z；n=1时就是"a"

**题解：**  
经典的递归运用之——全排列

void perm(int s,int e){
        
        if(s==e){
        
            for(int i=0;i<=e;i++){
        
                printf("%c",str[i]);
            }
            printf("\n");
            return ;
        }
        for(int i=s;i<=e;i++){
        
            swap(str[s],str[i]);
            perm(s+1,e);
            swap(str[s],str[i]);
        }
        return ;
    }

调用perm(0,n-1)即可

--------------------

## [G：九数组分数][G] ##

--------------------

**题意：**  
1~9，求构成两个数，满足num1/num2=1/3;

**题解：**  
同样是全排列问题

--------------------

## [H：数的划分][H] ##

--------------------

**题意：**  
给定一个整数n，求能划分的方案数

**题解：**  
经典递归运用之——整数划分

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]

int fx(int n,int m){
        
        if(n<1||m<1){
        
            return 0;
        }
        if(n==0||m==1)
            return 1;
        if(n<m){
        
            return fx(n,n);
        }
        if(n==m){
        
            return 1+fx(n,n-1);
        }
        if(n>m&&m>1){
        
            return fx(n,m-1)+fx(n-m,m);
        }
    }

调用fx(n,n)即可

--------------------

## [I：报数游戏][I] ##

--------------------

**题意：**  
n个人来回报数，当报的数为7的倍数或者包含7时，拍掌  
问编号为m的人，拍掌k次对应的数

**题解：**  
经典的约瑟夫环问题  
由于数据不大，可以直接模拟

--------------------

## [J：盒子游戏][J] ##

--------------------

**题意：**  
两个相同的盒子，开始时：一个装n个球，一个装一个球，Alice和Bob轮流操作  
每次选择一个球少的盒子，将盒子中的球倒光。  
当无法操作时，那个人就输了

**题解：**  
简单博弈

int fx(int n)
    {
        
        if(n==1)
            return 0;
        if(n%2==1)
            return fx(n/2);
        return n/2;
    }

判断fx(n)即可

[A]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=0
[B_I]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=1
[C]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=2
[D]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=3
[Link 1]: https://blog.csdn.net/boliu147258/article/details/104348667
[E]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=4
[F]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=5
[G]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=6
[H]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=7
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200302230101732.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70
[I]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=8
[J]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1078&pid=9