2014 第五届蓝桥杯软件本科A组预赛题解（填空及代码填空）

今天药忘吃喽~ 2022-08-26 01:23 133阅读 0赞

第一题：

标题：猜年龄  
  
  
小明带两个妹妹参加元宵灯会。别人问她们多大了，她们调皮地说：“我们俩的年龄之积是年龄之和的6倍”。小明又补充说：“她们可不是双胞胎，年龄差肯定也不超过8岁啊。”  
  
  
请你写出：小明的较小的妹妹的年龄。

注意： 只写一个人的年龄数字，请通过浏览器提交答案。不要书写任何多余的内容。

分析：暴力1---100之间的值，很快会计算出来，或者手算也可以麻烦一点。

答案是：10 因为10 \* 15 =150 和是25 150 / 25 = 6，所以...

第二题 ：

标题：神奇算式  
  
  
由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。  
  
  
比如：  
  
  
210 x 6 = 1260  
8 x 473 = 3784  
27 x 81 = 2187  
  
  
都符合要求。  
  
  
如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。  
  
  
请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）。

分析：我写的时候是两次循环，第一次循环枚举一位的和三位的，第二次枚举二位数和二位数的，最后得到结果。

答案：12 （注意是四个不同的数字，算出15的！没有看这句活吧。（说说自己））

分别是。

3 501

3 510

6 201

6 210

8 473

9 351

15 93

21 60

27 81

21 87

30 51

35 41

第三题：切面条

一根面条,从中间切一刀,可以得到2根,若先对折一下再切,可以得到3根,若对折2次再切,可以得到5根面条,现在问若对折10次后再切,可以得到几根面条?

//这个我直接当场折叠了下，然后估算pow(2,10) + 1 与前几次吻合就直接开始写答案了

##### 解题思路 #####

切面条时, 切开的面条只会有2种情况:1是成为独立的面条,2是会和其它面条相连,那么,现在把和其它面条的称之为一个'结',当不计算这些'结'时,折了几次之后切完面条应该为2^(n+1)根:

[?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>/*</code> 
     </div> 
     <div> 
      <code>折N次后切&nbsp;&nbsp;&nbsp; 面条根数</code> 
     </div> 
     <div> 
      <code>0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2</code> 
     </div> 
     <div> 
      <code>1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4</code> 
     </div> 
     <div> 
      <code>2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 8</code> 
     </div> 
     <div> 
      <code>3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 16</code> 
     </div> 
     <div> 
      <code>*/</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

下来,再计算'结'的个数,由于一个'结'存在之后就不会消除,所以下一状态'结'数量就是当前结数量 + 对折后创造的'结'数量.而对折后创造的'结'数量就是当前面条的根数:

[?][Link 1]

最后,由于1个结相连了两根面条,所以当折了N次后,面条根数就是总共面条数 - 结数量:

[?][Link 1]

第四道 ;

如果要在n个数据中挑选出第一大和第二大的数据（要求输出数据所在位置和值），使用什么方法比较的次数最少？我们可以从体育锦标赛中受到启发。8个选手的锦标赛，先两两捉对比拼，淘汰一半。优胜者再两两比拼...直到决出第一名。  
  
  
  
  
  
  
第一名输出后，只要对黄色标示的位置重新比赛即可。  
  
  
  
  
下面的代码实现了这个算法（假设数据中没有相同值）。  
  
  
  
  
代码中需要用一个数组来表示图中的树（注意，这是个满二叉树，不足需要补齐）。它不是存储数据本身，而是存储了数据的下标。  
  
  
  
  
第一个数据输出后，它所在的位置被标识为-1  
  
  
答案：

if(a[b[k1]] > a[b[k2]])

好吧。。。又错了！  
  
锦标赛 示例代码

//  pk(      a    ,  b,    2*n-1, 0,   b[0]);
    //重新决出k号位置，v为已输出值
    #include <stdio.h>
    #include <stdlib.h>
    void pk(int* a, int* b, int n, int k, int v)
    {
        int k1 = k*2 + 1;
        int k2 = k1 + 1;
         
        if(k1>=n || k2>=n){
            b[k] = -1;
            return;
        }
         
        if(b[k1]==v)
            pk(a,b,n,k1,v);
        else
            pk(a,b,n,k2,v);
         
        //重新比较
        if(b[k1]<0){
            if(b[k2]>=0)
                b[k] = b[k2];
            else
                b[k] = -1;
            return;
        }
         
        if(b[k2]<0){
            if(b[k1]>=0)
                b[k] = b[k1];
            else
                b[k] = -1;
            return;
        }
         
        if(a[b[k1]] > a[b[k2]]) //填空
            b[k] = b[k1];
        else
            b[k] = b[k2];
    }
     
    //对a中数据，输出最大，次大元素位置和值
    void f(int* a, int len)
    {
        int n = 1;
        while(n<len) n *= 2;// manshugeshu
         
        int* b = (int*)malloc(sizeof(int*) * (2*n-1));
        int i;
        for(i=0; i<n; i++){
            if(i<len)
                b[n-1+i] = i;
            else
                b[n-1+i] = -1;
        }
         
        //从最后一个向前处理
        for(i=2*n-1-1; i>0; i-=2){
            if(b[i]<0){
                if(b[i-1]>=0)
                    b[(i-1)/2] = b[i-1];
                else
                    b[(i-1)/2] = -1;
            }
            else{
                if(a[b[i]]>a[b[i-1]])
                    b[(i-1)/2] = b[i];
                else
                    b[(i-1)/2] = b[i-1];
            }
        }
         
        //输出树根
        printf("%d : %d\n", b[0], a[b[0]]);
         
        //值等于根元素的需要重新pk
        pk(a,b,2*n-1,0,b[0]);
         
        //再次输出树根
        printf("%d : %d\n", b[0], a[b[0]]);
         
        free(b);
    }
     
     
    int main()
    {
        int a[] = {54,55,18,16,122,17,30,9,58};
        f(a,9);
    }

第五道：史丰收速算   
史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!  
  
速算的核心基础是：1位数乘以多位数的乘法。  
  
其中，乘以7是最复杂的，就以它为例。  
  
因为，1/7 是个循环小数：0.142857...，如果多位数超过 142857...，就要进1  
  
同理，2/7, 3/7, ... 6/7 也都是类似的循环小数，多位数超过 n/7，就要进n  
  
下面的程序模拟了史丰收速算法中乘以7的运算过程。  
  
乘以 7 的个位规律是：偶数乘以2，奇数乘以2再加5，都只取个位。  
  
乘以 7 的进位规律是：  
满 142857... 进1,  
满 285714... 进2,  
满 428571... 进3,  
满 571428... 进4,  
满 714285... 进5,  
满 857142... 进6  
  
请分析程序流程，填写划线部分缺少的代码。  
  
  
  
//计算个位  
int ge\_wei(int a)  
\{   
if(a % 2 == 0)  
return (a \* 2) % 10;  
else  
return (a \* 2 + 5) % 10;  
\}  
  
  
//计算进位  
int jin\_wei(char\* p)  
\{   
char\* level\[\] = \{   
"142857",  
"285714",  
"428571",  
"571428",  
"714285",  
"857142"  
\};  
  
char buf\[7\];  
buf\[6\] = '\\0';  
strncpy(buf,p,6);  
  
int i;  
for(i=5; i>=0; i--)\{   
int r = strcmp(level\[i\], buf);  
if(r<0) return i+1;  
while(r==0)\{   
p += 6;  
strncpy(buf,p,6);  
r = strcmp(level\[i\], buf);  
if(r<0) return i+1;  
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_; //填空  
\}  
\}  
  
return 0;  
\}  
  
  
//多位数乘以7  
void f(char\* s)  
\{   
int head = jin\_wei(s);  
if(head > 0) printf("%d", head);  
  
char\* p = s;  
while(\*p)\{   
int a = (\*p-'0');  
int x = (ge\_wei(a) + jin\_wei(p+1)) % 10;  
printf("%d",x);  
p++;  
\}  
  
printf("\\n");  
\}  
  
  
int main()  
\{   
f("428571428571");  
f("34553834937543");  
return 0;  
\}  
  
  
答案：return i;

[Link 1]: http://blog.sbw.so/Article/index/title/%E8%93%9D%E6%A1%A5%E6%9D%AF2014%E5%B9%B4C%5CC++A%E7%BB%84-%E5%88%87%E9%9D%A2%E6%9D%A1.html#