【蓝桥杯c++(Python)每日练习】每日刷题day5:快排问题,抽签,方格填数

Hello,大家好我是[上进小菜猪],一个有趣的全栈博主,欢迎关注,多多关照
欢迎大家找我合作学习(文末有VX与公众号 想进学习交流群or学习资料or一起刷题 欢迎++)
苟怀四方志,所在可游盘,一起加油进步!

一,快排问题

标签java培训:2016,省赛,代码补全填空题

题目描述

本题为代码补全填空题,请将题java编译器目中给出的源代码补全,并复制到右侧代码框中,选择对应的编译语言(C/Java)后进行提交。若题目中给出的源代码语言不唯一,则只需选择其一进行补全提交即可。复制后需将源javaee代码中填空部分的下划线删掉,填java模拟器上你的答案。提交后若未能通过,除考虑填空部分出错外,还需注意是否因在复制后有改动非填空部分产生错误。
排序在各种场合经常被用到算法是什么。 快速排序是十分常用的高效率的算法
其思想是:先选一个“标尺”,用它把整个队列过一c#教程遍筛子,以保证:其左边的元素都不大于它,其右边的元素都不小于它。
这样,排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。
下面的代码是一种实现,请分析并填写划线部分缺少的代码。
源代码

#include <stdio.h>
void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
    _____________________;
    return j;
}
void quicksort(int a[], int p, int r)
{
    if(p<r){
        int q = partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}
int main()
{
    int i;
    int a[] = {50,49,48,48,47,46,1,3,5,2,4,6,30,30,30,30};
    int N = 16;
    quicksort(a, 0, N-1);
    for(i=0; i<N; i++) printf("%d.", a[i]);
    printf("\n");
    return 0;
}

答案:

swap(a,p,j);

总结:考察快速排序双指针,不熟算法是什么悉难度较大。

二,抽签

题目描述
本题为代码补全填空题,请将题目中给出的源代码补全,并复制到右侧代码框中,选择对应的编译语言(C/Java)后进行提交。若题目中给出的源代码语言不唯一,则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉,填上你的答案。提交后若未能通过算法工程师,除考虑填空部分出错外,还需注意是python123否因在复制后有改c#为什么用的人很少动非填java编译器空部分产生错误。
X星球要派出一个 5 人组成的观察团前往 W 星。

其中:
A 国python可以做什么工作最多可以派出 4 人。
B 国最多可以派出 2 人。
C 国最多可c#教程以派出 2 人。
....

那么最终派往 W 星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个python问题。 数组 a[] 中既是每个国家可以派出的最多的名额。 程序执行结果为:

DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略,总共101行)

下面的代码就是为了这个目的的,请仔细阅读源码,并填写划线部分缺少的代码。

源代码
C

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[])
{
    int i,j;
    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }
    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        ______________________;  //填空位置
    }
}
int main()
{    
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}

答案:

f(a,k+1,m-j,b);  //填空位置

总结:经典的递归题目

三,方格填数

题目描述
本题为填空题,只需要算c#面试题出结果后,在代码中使用输出语句将所填结果算法输出即可。

   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

java培训入 00 ~ 99 的数字。要求:连续的两个数字不能相邻。 (左右、上下、对角都算相邻)

一共有多少种可能的填算法的空间复杂度是指数方案?

运行限制 最大运行时间:1s 最大运行内存: 128M

答案:

1580

分析
【蓝桥杯c++(Python)每日练习】每日刷题day5:快排问题,抽签,方格填数

#include<bits/stdc++.h>
using namespace std;
bool check(int a[])
{
    if(abs(a[0]-a[1])==1||
       abs(a[0]-a[4])==1||
       abs(a[0]-a[5])==1||
       abs(a[0]-a[3])==1||
       abs(a[1]-a[2])==1||
       abs(a[1]-a[4])==1||
       abs(a[1]-a[5])==1||
       abs(a[1]-a[6])==1||
       abs(a[2]-a[5])==1||
       abs(a[2]-a[6])==1||
       abs(a[3]-a[4])==1||
       abs(a[3]-a[8])==1||
       abs(a[3]-a[7])==1||
       abs(a[4]-a[5])==1||
       abs(a[4]-a[7])==1||
       abs(a[4]-a[8])==1||
       abs(a[4]-a[9])==1||
       abs(a[5]-a[6])==1||
       abs(a[5]-a[8])==1||
       abs(a[5]-a[9])==1||
       abs(a[6]-a[9])==1||
       abs(a[7]-a[8])==1||
       abs(a[8]-a[9])==1
       )
    {
        return false;
    }
    return true;
}
int main()
{
    int a[11]={0,1,2,3,4,5,6,7,8,9},sum=0;
    while(next_permutation(a,a+10))
    {
        bool b=check(a);
        if(b)
        {
            sum++;
        }
    }
    cout<<sum<<endl;
return 0;
}

*python123*今日总结:
快排和全排列问题。**

四,END

关注作者,持续阅读作者的文章,一起学习更多知识!
[点击关注,联系作者,进入群聊,一起刷题]

如果有更优解法及其思路,欢迎讨论算法工程师