| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1892 人关注过本帖
标题:一道数组的程序题,帮帮忙
只看楼主 加入收藏
yang158
Rank: 1
等 级:新手上路
帖 子:47
专家分:0
注 册:2019-3-12
结帖率:16.67%
收藏
 问题点数:0 回复次数:6 
一道数组的程序题,帮帮忙
(1).  设计一个程序,完成以下功能:

a)    产生一个20个随机数组成的数组,编写快速排序算法完成这些数从小到大排序,并将排序后结果输出;(最好能打印每轮排序结果)

b)    输入其中任何一个数字,编写折半查找算法查找该元素在排序后数组中的位置;

c)     利用分治法求解这组数中的top n元素,既是这组数中第n(n<20)大的数据。
搜索更多相关主题的帖子: 数组 排序 结果 算法 元素 
2020-12-21 15:45
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏(1)
得分:0 
调用标准函数行不?

程序代码:
#include <iostream>
#include <algorithm>
#include <random>
//using namespace std;

int main( void )
{
    int arr[20];

    // a) 产生一个20个随机数组成的数组,编写快速排序算法完成这些数从小到大排序,并将排序后结果输出
    {
        std::generate( std::begin(arr), std::end(arr), [mt=std::mt19937{std::random_device{}()},dis=std::uniform_int_distribution<>(0,99)]()mutable{return dis(mt);} );
        std::sort( std::begin(arr), std::end(arr) );
        std::copy( std::begin(arr), std::end(arr), std::ostream_iterator<decltype(*arr)>(std::cout," ") );
        std::cout << std::endl;
    }

    // b) 输入其中任何一个数字,编写折半查找算法查找该元素在排序后数组中的位置
    {
        std::remove_cvref_t<decltype(*arr)> n;
        if( !(std::cin>>n) )
            return 1;
        auto p = std::lower_bound( std::begin(arr), std::end(arr), n );
        if( p==std::end(arr) || *p!=n )
            std::cout << "没发现.\n";
        else
            std::cout << std::distance(std::begin(arr),p) << std::endl;
    }

    // c) 利用分治法求解这组数中的top n元素,既是这组数中第n(n<20)大的数据
    // 这就奇怪了呀,数组已经排序好了,第i大元素就是 arr[20-1-i] 呀
    // 好吧,假设我就当数组没排序过
    {
        size_t n;
        if( !(std::cin>>n) || n>=std::size(arr) )
            return 1;
        std::nth_element( std::begin(arr), std::next(std::begin(arr),std::size(arr)-1-n), std::end(arr) );
        std::cout << arr[std::size(arr)-1-n] << std::endl;
    }
}
2020-12-21 16:25
yang158
Rank: 1
等 级:新手上路
帖 子:47
专家分:0
注 册:2019-3-12
收藏
得分:0 
回复 2楼 rjsp
大哥,你这个我看的很蒙,没看懂啊
2020-12-23 22:36
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
先讲随机数

C语言的随机数函数是 srand / rand
srand 的问题是,用什么作为随机种子?如果种子并不随机的话,那么随机序列就完全确定了。
通常,使用当前时间作为随机种子。然而有两个缺点:第一,在足够短的时间内,当前时间是不变的;第二,当前时间是可以被人预估或预设的。
rand 的问题是,它的随机数范围绝大多数时并不是用户需要的范围,需要经过复杂的缩放,。另外,它只能产生均匀分布的随机数。

C++的解决办法是
提供多种随机数算法,有的算法速度快,有的算法效果好,……。比如常用的 MT19937伪随机数生成算法。
提供一个真随机数,也就是 std::random_device。一般只在关键地方(比如作随机算法的种子)才使用它,因为它很珍贵,一旦耗尽需要很长时间才能新生。
提供多种分布器,将随机数分布到指定范围,及不同的几率分布。比如 均匀分布、正态分布、……。

示例,以下代码产生10组,每组20个元素,元素值在[0,99]范围内的序列
程序代码:
#include <iostream>
#include <algorithm>
#include <random>

int main( void )
{
    std::mt19937 gen{ std::random_device{}() };
    std::uniform_int_distribution<> dis(0,99);

    for( size_t cnt=10; cnt--; )
    {
        int a[20];
        for( auto& v : a )
            v = dis(gen);
        
        for( size_t i=0; i!=std::size(a); ++i )
            printf( "%d%c", a[i], " \n"[i+1==std::size(a)] );
    }
    return 0;
}

一种可能的输出是
程序代码:
61 36 85 27 78 19 85 28 33 97 87 34 47 38 34 89 3 12 74 98
77 28 29 48 16 6 38 80 44 67 54 55 92 61 40 31 6 98 53 35
78 71 20 55 62 39 89 72 21 32 82 53 7 36 49 50 72 8 96 17
42 88 47 12 45 31 23 2 8 93 42 17 89 92 7 35 99 98 13 0
20 24 37 86 43 34 91 24 56 10 30 39 40 38 82 11 53 91 64 82
22 91 83 65 42 92 68 83 10 49 50 3 71 65 46 60 52 87 14 9
47 94 47 8 99 7 14 78 50 43 2 98 19 69 51 55 54 98 33 11
9 89 53 52 63 93 69 29 28 70 6 33 72 78 14 43 21 9 61 42
46 64 69 20 72 28 96 92 46 81 57 0 69 87 7 8 62 17 81 24
33 86 0 42 48 62 91 53 24 58 24 56 90 86 38 80 83 5 58 16



------ 有时间再讲其它的吧,蛮耗费时间的 ------


[此贴子已经被作者于2020-12-24 10:41编辑过]

2020-12-24 10:40
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
再讲排序算法中最常用的快速排序

快速排序,在C语言中有 qsort,比较难用,且因为比较器是个无状态的函数,所以无法定制
在C++语言中有 std::sort,它的主体算法也是快速排序,但不仅仅是快速排序,因为它会根据情况自动切换成其它排序算法

对你的这道题目来说,如果你的老师禁止你使用标准库函数,要你手写快速排序算法的话,那也简单,例如
程序代码:
void quicksort( int a[], size_t len )
{
    if( len <= 1 )
        return;

    int key = a[0];
    size_t i=0, j=len-1;
    for( ; i!=j; )
    {
        for( ; i!=j && !(a[j]<key); --j );
        a[i] = a[j];

        for( ; i!=j && !(key<a[i]); ++i );
        a[j] = a[i];
    }
    a[i] = key;
    quicksort( a, i );
    quicksort( a+i+1, len-i-1 );
}
2020-12-24 12:27
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
既然有了快速排序,那顺便将你题目中最后一个问题“第k大”解决掉

快速排序是每一个元素都排,而“第k大”只需要确保 k位之前的数都小于等于第k个数 且 k位之后的数都大于等于第k个数 就行。
也就是只需要在 快速排序 算法中,只排序k所在的那半段就可以了。
在快排算法的基础上更改以下最后的递归,也就是
程序代码:
void nth_element( int a[], size_t len, size_t nth )
{
    if( len <= 1 )
        return;

    int key = a[0];
    size_t i=0, j=len-1;
    for( ; i!=j; )
    {
        for( ; i!=j && !(a[j]<key); --j );
        a[i] = a[j];

        for( ; i!=j && !(key<a[i]); ++i );
        a[j] = a[i];
    }
    a[i] = key;
    if( nth < i )
        return nth_element(a, i, nth);
    if( nth > i )
        return nth_element(a+i+1, len-i-1, nth-i-1);
}


顺便说一下,C++标准库有求“第K大”的函数,名字叫 std::nth_element
2020-12-24 12:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
折半查找算法那是最简单的算法之一了,不多说

程序代码:
// 返回第一个大于等于value的元素的下标
size_t lower_bound( const int a[], size_t len, int value )
{
    const int* p = a;
    for( size_t n=len; n>0; )
    {
        if( p[n/2] < value )
        {
            p += n/2+1;
            n -= n/2+1;
        }
        else
            n /= 2;
    }
    return p-a;
}


顺便说一下,
C标准库的折半查找函数名 bsearch
C++标准库的折半查找函数名 std::binary_search / std::equal_range / std::lower_bound / std::upper_bound

------ 结束,全剧终 ------
2020-12-24 13:08
快速回复:一道数组的程序题,帮帮忙
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019876 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved