VC知识库BLOG-杨老师之Blog-算法征集

算法征集

本人在一个工程任务中,需要完成“在9个整数中，找到中值”。
比如：1,3,5,7,9,2,4,6,8 的中值是5。

看似非常简单的一个小问题，但由于每秒钟需要调用大约10万多次，因此我需要一个快速算法，不考虑空间浪费，只要求比较语句尽可能的少。

有好的想法吗？欢迎抛砖引玉......

posted on 2006-04-02 11:46 杨老师的茅屋阅读(2822) 评论(26) 编辑收藏

# re: 算法征集
sevencat
Posted @ 2006-04-02 12:01
抛块石头先。
# re: 算法征集
sevencat
Posted @ 2006-04-02 12:01
void insertion_sort(int array[], unsigned int first, unsigned int last)
{
        int i,j;
        int temp;
        for (i = first+1; i<=last;i++)
        {
                temp = array[i];
                j=i-1;

                //与已排序的数逐一比较, 大于temp时, 该数移后
                while((j>=first) && (array[j] > temp))
                {
                        array[j+1] = array[j];
                        j--;
                }

                array[j+1] = temp;
        }
}
# re: 算法征集
乾坤一笑
Posted @ 2006-04-02 13:47

查中值又不是排序，不需要O²算法拉。
偶来丢个石子，嘿嘿～
请看拙文《位图算法－找中值》
# re: 算法征集
清风雨
Posted @ 2006-04-02 20:42
既然要调几万次，而且只要找到中值。
第一次查找，找到了，以后直接返回不就得了？
不知是否理解有错。
# re: 算法征集
小刀人
Posted @ 2006-04-02 21:50
既然是定下来9个数求中值，可否就根据需要先用改进的选择排序，选择到最大的（或最小的）5个数，然后输出第5个数就Ok了。
# 没看懂题目的具体要求，我就随便写一个：
周星星
Posted @ 2006-04-03 09:52

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char* argv[])
{
    int arr[9] = { 1,3,5,7,9,2,4,6,8 };
    nth_element( &arr[0], &arr[4], &arr[9] );
    cout << arr[4] << endl;

    return 0;
}
# re: 算法征集
imjj
Posted @ 2006-04-03 10:29
char find_center(char datas[])
{
        char flag[10] = {0};
        char sum = 0;
        for(char i = 0; i < 9; i++)
        {
                flag[datas[i]]++;
                sum += datas[i];
        }

        char m = sum / 9;
        m++;
        char i = m;
        while(flag[i] == 0)       // 对于有些数据应该是i++,但偶还没想好怎么去处理
                i--;
        return i;
}
# re: 算法征集
heroboy
Posted @ 2006-04-03 10:54
unsigned char findc(char* data)
{
unsigned char flag[256];
memset(flag,0,256);
++flag[data[0]];
++flag[data[1]];
++flag[data[2]];
++flag[data[3]];
++flag[data[4]];
++flag[data[5]];
++flag[data[6]];
++flag[data[7]];
++flag[data[8]];
unsigned char * p=flag;
int count=0;
while(count<5)
{
count+=*p++;
}
return p-flag-1;
}
程序未测试。
如果能把while循环解开，那程序中就没有跳转了，虽然有if:
count+=flag[0];
if (count>=5) return 0;
count+=flag[1];
if (cout>=5) return 1;
...
...
# re: 算法征集
anonymous
Posted @ 2006-04-03 12:34
用"基数排序"的原理.

int i, ret=0;
unsigned char cnt[9]={0};
unsigned char in[9]={1,3,5,7,9,2,4,6,8};

for(i=0; i<9; ++i)
   ++cnt[in[i]-1];

for(i=0; i<9; ++i){
   ret+=cnt[i];
   if(ret>=5){
      ret=i+1;
      break;
   }
}

感觉和一笑那个差不多:-)
# re: 算法征集
oshj
Posted @ 2006-04-03 13:06
哈哈，我也征集

大矩形 x*y 中可排小矩形 m*n 的最大个数
分两个方式：
1、m*n不限制方向
2、m*n限制方向
# re: 算法征集
abcs
Posted @ 2006-04-03 13:19
/* （没运行过）直接用基数排序全排出来好了，把循环展开之后一个if都没有了 */

#include <memory.h>

#define L(x) ((x) & 0x0F)
#define H(x) ((x) >> 4)

unsigned char median_of_nine(unsigned char *a)
{
unsigned char c[16];
unsigned char r[9], r2[9];
int i;
memset(c, 0, sizeof(c));
for(i = 0; i < 9; i++)
{
c[L(a[i])]++;
}
for(i = 1; i < 16; i++)
{
c[i] += c[i - 1];
}
for(i = 8; i >= 0; i--)
{
r[--c[L(a[i])]] = i;
}
memset(c, 0, sizeof(c));
for(i = 0; i < 9; i++)
{
c[H(a[i])]++;
}
for(i = 1; i < 16; i++)
{
c[i] += c[i - 1];
}
for(i = 8; i >= 0; i--)
{
r2[--c[H(a[r[i]])]] = r[i];
}
return a[r2[4]];
}
# re: 算法征集
anonymous
Posted @ 2006-04-03 13:49
九相异数中位数必为五. 一至九当中一个数出现超过5次则这个数必为中位数.
根据这两个命题可以对一些特殊数列在第一次基排分类后就直接得出中位数是什么.
# to oshj //re: 算法征集
一笑
Posted @ 2006-04-03 19:21
oshj这个问题没难度，是搜索算法课的入门题:) 最简单的回溯法就可以解，如果用广度优先搜索就更快。你不如做做在矩阵里面放L骨牌的题目.
L骨牌是这样子的：
×
×
××
放在m*n的矩阵里，L骨牌可旋转。
# re: 算法征集
马甲多成毛了,一个都不牛
Posted @ 2006-04-04 00:31
俺以为数的二进制形式分析起来比较容易看出最大的前面5个,算法实现起来效率好像比较高,不过我不会写程序,都怪杨老师当年没有教我啊
# re: 算法征集
liaobird
Posted @ 2006-04-04 17:09
很多同学没审好题:“在9个整数中，找到中值”
最大值是一个[整数]，并不一定是9.
# re: 算法征集
liaobird
Posted @ 2006-04-04 17:42
liaobird
杨老师，你好：
  我以前做过图象处理，在图象滤波中有一种叫中值滤波。就是您在上面提到的算法。因为中值算法效率低下，所以外国的一个学者提出用伪中值，就是前三个取中值,中三个取中值，后三个取中值，三个结果取中值。效率比较快，在一定程度上也达到中值滤波的效果。
我的程序是这样的:
typedef unsigned char BYTE;

BYTE in[9]={1,3,5,7,9,2,4,6,8};

inline BYTE val(BYTE& a,BYTE& b,BYTE& c)
{
if(b>c) return b;
else return min(a,c);
}
inline BYTE mid(BYTE a,BYTE b,BYTE c)
{
return a>b ? val(a,b,c) : val(b,a,c);
}

int main()
{
  BYTE m = mid(
               mid(in[0],in[1],in[2]),
               mid(in[3],in[4],in[5]),
               mid(in[6],in[7],in[8]));
}
# 感谢 liaobird
杨老师
Posted @ 2006-04-04 22:41
非常感谢,原来国外是这么处理的呀。非常感谢，我看看滤波后的效果。
# re: 算法征集
sevencat
Posted @ 2006-04-05 20:49
还是专业人士强啊。
# re: sevencat
清风雨
Posted @ 2006-04-05 21:29
这个就过于媚洋了。并没有实质改进，照样都算了所有数。
# re: 算法征集
liaobird
Posted @ 2006-04-06 09:21
我们应该是拿来主义吧。即使别人没提出这个思想，我们可能也会想到，关键在于解决问题。
要找一组数的中值，本身就必须遍历所有的数。每个数参与计算的次数应该>=1,算法的优化只是在保证得到结果的条件下计算量最小,即每个数计算的次数趋近于1，而不可能<1。如果那样的话，得到的值肯定是不对的,除非在先验条件下能知道数据本身的特性。
# re: 算法征集
shouqiu
Posted @ 2006-04-10 16:56
#define SORT_3(a, b, c, temp) /*这个宏省了，光用比较和赋值就够了*/
#define MID_3(a, b, c) \
    a < b ? (b < c ? b : (a < c ? c : a)) : (a < c ? a : (b < c ? c : b))
int midof(int nums[/*9*/])
{
#define DEFINE_N(i) *n##i = nums + i
#define SORT_NUMS(a, b, c) SORT_3(*n##a, *n##b, *n##c, temp)
    int DEFINE_N(0), DEFINE_N(1), DEFINE_N(2), DEFINE_N(3), DEFINE_N(4), DEFINE_N(5), DEFINE_N(6), DEFINE_N(7), DEFINE_N(8);
    int temp;
    SORT_NUMS(0, 1, 2);
    SORT_NUMS(3, 4, 5);
    SORT_NUMS(6, 7, 8);
    SORT_NUMS(0, 3, 6);
    SORT_NUMS(1, 4, 7);
    SORT_NUMS(2, 5, 8);
    return MID_3(*n2, *n4, *n6);
}
# re: 算法征集
shouqiu
Posted @ 2006-04-10 17:02
这个算法需要14~21次比较；0~18次交换。虽然没证明比基于快速排序的方法快，但至少这个算法能够很容易地把循环相关的比较省掉。经测试，本机(P4 3G, 1G RAM)每秒能进行100万次。
# re: 算法征集
杨老师救命啊.
Posted @ 2006-08-03 22:43
case DISPID_BEFORENAVIGATE2:
m_spWebBrowser2->Navigate(newURL, &pDispParams->rgvarg[4],&pDispParams->rgvar[3],&pDispParams->rgvarg[2],&pDispParams->rgvarg[1]);

如何在dll的形式中修改 [PostData As Variant,] _
    [Headers As Variant])这两个参数.能帮忙给你显示语句??
像我这样改就不行.m_spWebBrowser2->Navigate(newURL, &pDispParams->rgvarg[4],&pDispParams->rgvarg[3],
&pDispParams->rgvarg[2], "Referer:http://china.com/");

我想修改在HTTP请求头中来源的信息浏览器的版本以及操作系统的版本等信息。
扬老师抽个空帮忙一下.
发到我的信箱:amanl@hotmail.com
# re: 算法征集
困惑
Posted @ 2006-08-06 21:52
我征个情人行吗:P
# re: 算法征集
CJF
Posted @ 2006-09-19 10:12
我有个方法不知道行不行,9个数字相加再除以9,得到平均数,中直就是离平均数最近的数字,没个数减中直取摸,摸最小的就是中直.
# re: 算法征集
myownparadise
Posted @ 2008-06-18 16:29
记得有道数学题目，是这样说的：
8个乒乓球手比赛，需要选出冠亚军，问最少需要打几场比赛？（其中假设球技高的总能打赢球技低的）
答案是9次。

第一场，两两一比赛，打了四场，只剩四人；
第二场，两两一比赛，打了两场,剩下两人；
第三场，最后两人比赛，分出冠军。到此为止，共进行了七场比赛。

要选出亚军，是这样说的，亚军只可能被冠军打败，而冠军只打了三场比赛，那么只要让与冠军交手的三人比赛，就能找出亚军了。而三个人比赛，找出球技最高的，只需比赛两场。因此答案为9。

不知通过这个题目，能否给大家一点启示。但难题是计算机世界可不如现实世界，在计算机中必须记录下与冠军比赛的人，这又需要开支。

我有个比较好的稳妥的办法，9个数字吗，利用选择排序，找出最大的，需要8次比较，再从剩下的8个中找出最大的（在9个数中相当于第二大），需要7次，依次类推，需要8+7+6+5+4=30次才能找到第五大的，即是我们要的中值。但我想这个算法肯定不是最快的。

标题

姓名

主页


验证码	*

内容

Remember Me?

登录使用高级评论 Top

[使用Ctrl+Enter键可以直接提交]

导航

随笔分类

随笔档案

文章档案

相册

统计