数值算法.

which

首先我不知道这样的一个算法问题，应当用什么方式来解决.

比如我有N组数据.

26,35,1203,5490....
25 34 1202,3442,5489,12324.....
......

1. 每组数据的个数,不相同. 但是它们按照由小到大的顺序排序.
2. 这些数据可能会有相似.比如26和25差1. 35和34差1.
3. 而且它们的位置未必会一一对应,比如 26可以对25, 35可以对34, 1203可以对1202.如果有百分之80以上的数据相差在0-1这样.就认为这两组数据是相似的.
4. 给出一组新的数据比如26,1203,5491.... 可以给出它和存在的某些数据是相似的.

这样的算法属于哪一类的算法?可以有什么好的办法?

cobras

1. 
   
2. #include <stdlib.h>
   
3. 
   
4. void skip_list(const int **a, int *alen, const int num)
   
5. {
   
6.         const int *pa;
   
7.         int i;
   
8. 
   
9.         pa = *a;
   
10.         for (i = 0; i < *alen; i++) {
    
11.                 if (pa[i] + 1 >= num) {
    
12.                         break;
    
13.                 }
    
14.         }
    
15.         *a = pa + i;
    
16.         *alen -= i;
    
17. }
    
18. 
    
19. int compare_list(const int *a, int alen, const int *b, int blen)
    
20. {
    
21.         int count;
    
22. 
    
23.         count = 0;
    
24.         while (alen > 0 && blen > 0) {
    
25.                 skip_list(&a, &alen, *b);
    
26.                 if (abs(*a - *b) <= 1) {
    
27.                         a++;
    
28.                         alen--;
    
29.                         b++;
    
30.                         blen--;
    
31.                         count += 2;
    
32.                 }
    
33.                 skip_list(&b, &blen, *a);
    
34.                 if (abs(*a - *b) <= 1) {
    
35.                         a++;
    
36.                         alen--;
    
37.                         b++;
    
38.                         blen--;
    
39.                         count += 2;
    
40.                 }
    
41.         }
    
42.         return count;
    
43. }
    
44. 
    
45. /* TEST */
    
46. 
    
47. #include <stdio.h>
    
48. 
    
49. #define LEN(a) (sizeof(a)/sizeof((a)[0]))
    
50. 
    
51. int main(void)
    
52. {
    
53.         static int a[] = {26,35,1105,1203,5490,12322};
    
54.         static int b[] = {25,34,1202,3442,5489,12324};
    
55.         int retval;
    
56. 
    
57.         retval = compare_list(a, LEN(a), b, LEN(b));
    
58.         if (retval * 100 / (LEN(a) + LEN(b)) >= 80) {
    
59.                 printf("same: %d/%d\n", retval, LEN(a)+LEN(b));
    
60.         }else {
    
61.                 printf("not same: %d/%d\n", retval, LEN(a)+LEN(b));
    
62.         }
    
63.         return 0;
    
64. }
    

复制代码

which

原帖由 cobras 于 2009-2-22 17:33 发表

#include

void skip_list(const int **a, int *alen, const int num)
{
        const int *pa;
        int i;

        pa = *a;
        for (i = 0; i < *alen; i++) {
                if (pa + 1 >= num) {
                        break;
                }
        }
        *a = ...

哥们首先感谢你辛苦的写了一些代码,但是我不需要代码,我需要的就是用什么样的算法来实现它.

另外你的代码不符合要求啊.我上面提供的那两组数据应该是属于相似的.

bidongliang

如果把两个数a, b的“相等”定义为: |a - b| <= 1，那任意两组数据是否相似的问题就变成了它们的元素是否有80%以上的“相等”，亦即两个集合的交集的元素个数占各自的80%以上。如果写程序的话可以对一组数据中的元素使用binary_search(用自定义的相等运算)，在另一组数据中查找是否有相同数据，然后统计个数就可以了。

cobras

原帖由 which 于 2009-2-22 18:34 发表


哥们首先感谢你辛苦的写了一些代码,但是我不需要代码,我需要的就是用什么样的算法来实现它.

另外你的代码不符合要求啊.我上面提供的那两组数据应该是属于相似的.

你再仔细看看测试数据，跟你的数据是不同的哦

cobras

原帖由 bidongliang 于 2009-2-22 23:00 发表
如果把两个数a, b的“相等”定义为: |a - b|  

这应该是最简单的算法，但是时间复杂度会高一点。（是n * log2(n)吗？）

drowsyboy

相似度计算？

不知道你的具体应用，你可以找找有关相似度计算方面的材料
重要的是，如何根据你的应用带定制你自己的相似度计算公式：）

A.com

相似度是个模糊问题,只能用策略来进行初始化.譬如楼主举的例子里面的相似度策略就是同位差.数组A减数组B得到的新数组,如果波动在1范围之内的超过80%就符合策略条件.