编程小练习（4）

zapline · 发表于 2010-2-28 13:30

题目：

随机生成500个大于1小于1000的正整数

计算这500个数中10个最大的数之和

blueapplez · 发表于 2010-2-28 15:21

#include "stdafx.h"
#include "windows.h"
#include "stdlib.h"
#include "time.h"

//不排序的方法里面用到的一个function
int GetMinIndex(WORD nSort[], int iCount)
{
    int iRet = 0;
    for (int i=1; i<iCount; i++)
    {
        if (nSort[iRet] > nSort[i])
        {
            iRet = i;
        }
    }
    return iRet;
}

int main(int argc, char* argv[])
{
    WORD nSort[500] = {0};
    srand(unsigned int(time(NULL)));
    for (int i=0; i<500; i++)
    {
        //2~999
        // 0~997 + 2  =>  2~999
        nSort[i] = rand()%998 + 2;  
    }
    WORD wCount = 0;

    //冒泡排序    
    for (i=0; i<500; i++)
    {
        WORD iminIndex = i;
        for (int j=i+1; j<500; j++)
        {
            if (nSort[i]>nSort[j])
            {
                nSort[i] ^= nSort[j];
                nSort[j] ^= nSort[i];
                nSort[i] ^= nSort[j];
            }
        }
    }
    for (i=490; i<500; i++)
    {
        wCount += nSort[i];
    }
    printf("冒泡排序的结果:%d \n", wCount);
    
    //下面是桶排序
    WORD wSortTemp[1000] = {0};
    for (i=0; i<500; i++)
    {
        wSortTemp[nSort[i]]++;
    }
    int j=0;
    for (i=0; i<1000; i++)
    {
        while (wSortTemp[i]--)
        {
            nSort[j] = i;
            j++;
        }
    }
    wCount = 0;
    for (i=490; i<500; i++)
    {
        wCount += nSort[i];
    }
    printf("桶排序的结果:%d\n", wCount);

    //下面是不排序
    WORD wSortBig[10] = {0};
    for (i=0; i<10; i++)
    {
        wSortBig[i] = nSort[i];
    }
    for (i=10; i<500; i++)
    {
        int iIndexMin = GetMinIndex(wSortBig, 10);
        if (wSortBig[iIndexMin] < nSort[i])
        {
            wSortBig[iIndexMin] = nSort[i];
        }
    }
    wCount = 0;
    for (i=0; i<10; i++)
    {
        wCount += wSortBig[i];
    }
    printf("不排序的结果:%d\n", wCount);

    return 0;
}

blueapplez · 发表于 2010-2-28 15:33

本帖最后由 blueapplez 于 2010-2-28 15:35 编辑

回复 2# blueapplez

其实这样有点不能说明问题，因为第一个排序就把原数组给修改了下面这样比较能说明问题

#include "stdafx.h"
#include "windows.h"
#include "stdlib.h"
#include "time.h"

//不排序的方法里面用到的一个function
int GetMinIndex(WORD nSort[], int iCount)
{
    int iRet = 0;
    for (int i=1; i<iCount; i++)
    {
        if (nSort[iRet] > nSort[i])
        {
            iRet = i;
        }
    }
    return iRet;
}

int main(int argc, char* argv[])
{
    WORD nSort[500] = {0};    
    WORD wCount = 0;

    //初始化数据...
    srand(unsigned int(124272));
    for (int i=0; i<500; i++)
    {
        //2~999
        // 0~997 + 2  =>  2~999
        nSort[i] = rand()%998 + 2;  
    }

    //冒泡排序    
    for (i=0; i<500; i++)
    {
        WORD iminIndex = i;
        for (int j=i+1; j<500; j++)
        {
            if (nSort[i]>nSort[j])
            {
                nSort[i] ^= nSort[j];
                nSort[j] ^= nSort[i];
                nSort[i] ^= nSort[j];
            }
        }
    }
    for (i=490; i<500; i++)
    {
        wCount += nSort[i];
    }
    printf("冒泡排序的结果:%d \n", wCount);
    
    //重置数据...
    srand(unsigned int(124272));
    for (i=0; i<500; i++)
    {
        //2~999
        // 0~997 + 2  =>  2~999
        nSort[i] = rand()%998 + 2;  
    }
    //下面是桶排序
    WORD wSortTemp[1000] = {0};
    for (i=0; i<500; i++)
    {
        wSortTemp[nSort[i]]++;
    }
    int j=0;
    for (i=0; i<1000; i++)
    {
        while (wSortTemp[i]--)
        {
            nSort[j] = i;
            j++;
        }
    }
    wCount = 0;
    for (i=490; i<500; i++)
    {
        wCount += nSort[i];
    }
    printf("桶排序的结果:%d\n", wCount);

    //重置数据...
    srand(unsigned int(124272));
    for (i=0; i<500; i++)
    {
        //2~999
        // 0~997 + 2  =>  2~999
        nSort[i] = rand()%998 + 2;  
    }
    //下面是不排序
    WORD wSortBig[10] = {0};
    for (i=0; i<10; i++)
    {
        wSortBig[i] = nSort[i];
    }
    for (i=10; i<500; i++)
    {
        int iIndexMin = GetMinIndex(wSortBig, 10);
        if (wSortBig[iIndexMin] < nSort[i])
        {
            wSortBig[iIndexMin] = nSort[i];
        }
    }
    wCount = 0;
    for (i=0; i<10; i++)
    {
        wCount += wSortBig[i];
    }
    printf("不排序的结果:%d\n", wCount);

    return 0;
}

chenyuzheng · 发表于 2010-2-28 15:52

本帖最后由 chenyuzheng 于 2010-2-28 16:33 编辑

#include "stdio.h"
#include "stdlib.h"
#define size 500
void main()
{ int r,i,j,max,isum=0;
   int a[size];                     
                                                        //观看了楼上的代码后,真是醍醐灌顶,所以这里应该加句srand(time(0))函数比较合乎情理.
for(i=0;i<500;i++){
       r=1+rand()%999;  //1到999之间的数
       a[i]=r;}
for(i=0;i<10;i++)
{ for(j=0;j<500-i;j++)
      if(a[j]<a[j+1])max=a[j+1]; 
      else max=a[j]; //找出10个最大的数
isum=max+isum; }
printf("%d",isum);
}

我没有误解题目意思吧?
请指教!

zapline · 发表于 2010-2-28 16:36

[quote]我没有误解题目意思吧?
请指教!
chenyuzheng 发表于 2010-2-28 15:52 [/quote]

for(i=0;i<10;i++)

{ for(j=0;j<500-i;j++)

if(a[j]<a[j+1])max=a[j+1];

else max=a[j]; //找出10个最大的数

isum=max+isum; }

这里排序/选最大算法有问题

题目是要 isum = 大小排名前十的10个数之和

chenyuzheng · 发表于 2010-2-28 16:49

本帖最后由 chenyuzheng 于 2010-2-28 16:52 编辑

不是吧!我就找了最大的10个数,其他数字大小我就不找.

for(j=0;j<500-i;j++)

{if(a[j]<a[j+1])max=a[j+1];

else max=a[j];}加括号吗?

zapline · 发表于 2010-2-28 17:24

不是吧!我就找了最大的10个数,其他数字大小我就不找.

for(j=0;j
chenyuzheng 发表于 2010-2-28 16:49

for(j=0;j<500-i;j++)

   {if(a[j]<a[j+1])max=a[j+1];

   else max=a[j];}

假设 4 2 1 3
用你的算法来获取最大的
4 < 2    不成立  max = 4
2 < 1    不成立  然后max就变成2了

所以最后得到的只是最后两个数的较大值

chenyuzheng · 发表于 2010-2-28 17:32

本帖最后由 chenyuzheng 于 2010-2-28 17:59 编辑

#include "stdio.h"
#include "stdlib.h"
#include"time.h" 
#define size 501
void main()
{ int r,i,j,max,isum=0,t;
int a[size]; 
srand(time(0));
for(i=0;i<500;i++)
{ r=2+rand()%998;
a[i]=r;}
for(i=0;i<10;i++)
{ for(j=0;j<500-i;j++)
if(a[j]<a[j+1])max=a[j+1];
else t=a[j],a[j]=a[j+1],a[j+1]=t;
isum+=max;
}
printf("%d\n",isum); 
}

..............
应该是这样了.
斑竹!!!这个应该没问题吧?

vienna · 发表于 2010-2-28 17:45

冗长的是我的

#include <iostream>
#include <ctime>

int main() {
        srand(unsigned (time(NULL)));

        //随机500个数字
        unsigned rand_no[500];
        for (int i = 0;i < 500;++i) {
                rand_no[i] = (rand()%998 + 2);
        }

        //冒泡啊冒泡
        for (int y = 0,temp;y < 500;++y) {
                for (int j = 499;j > y;j--) {
                        if (rand_no[j] > rand_no[j-1]) {
                                temp = rand_no[j];
                                rand_no[j] = rand_no[j-1];
                                rand_no[j-1] = temp; 
                        }
                }
        }

        //排序测试
//          for (int x = 0;x < 500;++x){
//                  std::cout << "  " << rand_no[x];
//          }

        //输出
        unsigned sum = 0;
        for (int x = 0;x < 10;++x) {
                sum += rand_no[x];
        }
        std::cout << sum << std::endl;
}

这个抄考别人的

#include <iostream>
#include <algorithm>
#include <ITERATOR>
#include <vector>
#include <ctime>

struct rand_from_1_to_1000 {
        int operator () () {
                return (rand()%998 + 2);
        }
};

int main() {
        srand(unsigned (time(NULL)));
        std::vector <int> v;
        std::generate_n(std::back_inserter(v), 500, rand_from_1_to_1000());  
        std::sort(v.begin(), v.end()); 

        unsigned sum = 0;
        for (int i = 499;i > 489;i--) {
                sum += v[i];
        }
        std::cout << sum << std::endl;
}

zapline · 发表于 2010-2-28 18:09

..............
应该是这样了.
斑竹!!!这个应该没问题吧?
chenyuzheng 发表于 2010-2-28 17:32

还是有问题
如果最后一个数不是最大的十个数之一则结果会错误
另外效率也非常低

帐号		自动登录	找回密码
密码			注册[Register]

[其他原创] 编程小练习（4）