StarHui


私信TA

用户名:uq_15565483691

访问量:459

签 名:

只要你想,世界就会出现奇迹!

等  级
排  名 363
经  验 4439
参赛次数 2
文章发表 24
年  龄 18
在职情况 学生
学  校 西安汽车职业大学
专  业 人工智能

  自我简介:

大一新生一枚 一起学习交流,请加V:StarHui0415

解题思路:
                    题前小磕:这一题一看题目就非常简单,但是为什么我还要写这个题解呢?这个代码改了好久....因为淋过雨,所以要帮你们撑伞!!!(好久没有写题解了,更新一下)

                    大致思路:

                    题目要求求出整个序列中第k大的数字减去第k小的数字的值m,并判断m是否为质数。一看第k大、第k小就知道必须要先排序。其次要知道第k大的数字和第k小的数字对应的下标是多少,第k小的数字下标是 k-1,第k大的下标是 n - k。如果不知道为什么的,建议回去复习一下数组(提示:下标)。这样就能得到需要判断的那个数了(暂时把这个数叫res)。接下来就是判断质数了。这里注意一个细节,就是质数的定义:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。(必须大于1)。而质数的判断方法有好几种,能相信做到这道题的应该都会吧!本题解使用的是优化的暴力筛选法(sqrt函数),如果不懂,就去百度一下吧!!!

                    具体步骤:

                                    1、排序(使用C语言的同学可以使用冒泡排序法或者快速排序法、C++的同学使用标准库函数sort即可,注意要使用algorithm头文件

                                    2、得到需要进行判断的数字res。res = nums[n - k] - nums[k - 1]

                                    3、判断是否为质数

注意事项:

                    1、排序如果使用冒泡排序法或者快速排序法,要注意边界范围,小心越界。(如果不会排序的,可以看我之前写的关于排序的题解,超级详细)

                    2、在进行质数判断前一定要判断那个数是否大于1(我就是因为,才没有通过)

                    3、质数判断时,要注意循环条件为i <= (int)sqrt(res),以防49这样的数字判断成质数

参考代码:

C++代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 10000;
int nums[N];

bool isprime(int x)
{
    if(x <= 1)//紧扣质数定义 如果小于等于1,直接返回false
        return false;
    else
    {
        int flag = 1;
        for(int i = 2;i <= (int)sqrt(x);i++)
        {
            if(x % i == 0)
                flag = 0;
        }
        if(flag == 1)
            return true;
        else
            return false;
    }
}

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> nums[i];

    sort(nums,nums + n);//进行排序,不要忘了头文件algorithm
    int res = nums[n - k] - nums[k - 1];//得到需要进行判断的数字

    if(isprime(res))//进行质数判断
    {
        cout << "YES" << endl;
        cout << res << endl;
    }
    else
    {
        cout << "NO" << endl;
        cout << res << endl;
    }
    return 0;
}

C代码

#include <stdio.h>
#include <math.h>

void quick_sort(int nums[],int l,int r)//快速排序法
{
    if(l >= r)
        return;
    int i = l - 1,j = r + 1,x = nums[(l + r) / 2];
    while(i < j)
    {
        do i++;while(nums[i] < x);
        do j--;while(nums[j] > x);
        if(i < j)
        {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j + 1,r);
}

int isprime(int x)//质数判断
{
    if(x <= 1)//如果小于等于1,直接退出
        return 0;
    else
    {
        int flag = 1;
        for(int i = 2;i <= (int)sqrt(x);i++)
        {
            if(x % i == 0)
                flag = 0;
        }
        if(flag == 1)
            return 1;
        else
            return 0;
    }
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    static int N = 10000;//防止数组太大,导致爆栈
    int nums[N];
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&nums[i]);
    }
    quick_sort(nums,0,n - 1);//快速排序法
    int res = nums[n - k] - nums[k - 1];//得到需要进行判断的数
    if(isprime(res))
    {
        printf("YES\n");
        printf("%d\n",res);
    }
    else
    {
        printf("NO\n");
        printf("%d\n",res);
    }
    return 0;
}


 

0.0分

3 人评分

  评论区