擂台：最长非升序子串的最优化算法

knight

现在考试太忙了
等有时间了再说吧

donms

写了个，还没充分测试，先看看！

int find_sub_string(char* p, char** position)
{
    char* max_pos = p;
    int   max_len = 1;
    char* pos = p;
    int   len = 1;
    if(*p == '\0')
    {   
        *position = p;
        return 0;
    }
    while(*(p+1) != '\0')
    {
        if((*(p+1)-*p) > 0)
        {
            if(len > max_len)
            {
                max_pos = pos;
                max_len = len;
            }
            pos = p+1;
            len = 1;
        }
        else
        {
            ++len;
        }
        ++p;
    }
    if(len > max_len)
    {
        max_pos = pos;
        max_len = len;
    }
    *position = max_pos;
    return max_len;
}

main()
{
    int n,i;
    char* pos;
    char p[] = "dfasgsdftffekloeqngalsdfdsaiwerh";
    n = find_sub_string(p, &pos);
    for(i = 0; i < n; ++i)
    {
        printf("%c",*(pos+i));
    }
    printf("\n");
}

aysten

你这个不完全,我给的例子能通过但是这个测试点却错了:
"acbcdc" 最长的非升序子串应当是"ccc",而你的结果是"cb"
不最长的并不一定要是相邻的.你的算法要重新从头想.加油!!!

donms

原来子串的理解是这样的啊！
——母串的顺序子集
和我以前的理解有点出入，不好意思！ ：）

itmwk

动态规划吧？

itmwk

偶写了一个，MATLAB的，例程如下：

clear
clc
%status是一单元数组，一行代表一种状态，第一个元素存储对应的字母，第二个元素代表对应长度，第三个元素为在ch_in中对应的序号，第四个元素为对应的字符串
%2004.1.11

ch_in=input('Please input the objective string:','s');
ch_len=size(ch_in,2);
size_sta=0;
if ch_len==1
    disp('Only one char???Please Input again!')
else
    ch_in_decrea=ch_in(ch_len:-1:1);
    ch_in=ch_in_decrea;
        for i=1:ch_len
                if i==1
            size_sta=1;
            status(1,={ch_in(1),1,1,ch_in(1)};
                else
            temp_numth=ones(1,size(status,1));
            for k=1:size(status,1)
                temp_numth(k)=status{k,1};
            end
            max_numtest2=find(temp_numth<=ch_in(i));
            if isempty(max_numtest2)
                size_sta=size_sta+1;
                status(size_sta,={ch_in(i),1,i,ch_in(i)};
            else
                max_numtest=find(temp_numth<ch_in(i));
                if ~isempty(max_numtest)
                    max_lentest=status{max_numtest(1),2};
                    max_numthtest=max_numtest(1);
                    for q=2:size(max_numtest,2)
                        if max_lentest<status{max_numtest(q),2}
                            max_lentest=status{max_numtest(q),2};
                            max_numthtest=max_numtest(q);
                        end
                    end
                    temp_len=status{max_numthtest,2}+1;
                    temp_equ=find([status{find([status{:,2}]==temp_len),1}]==ch_in(i));
                    if isempty(temp_equ)
                        temp_char=strcat(status{max_numthtest,4},ch_in(i));
                        size_sta=size_sta+1;
                        status(size_sta,={ch_in(i),temp_len,i,temp_char};
                        min_i=char(min(temp_numth(find(temp_numth>ch_in(i)))));
                        if ~isempty(min_i)
                            min_num=find(temp_numth==min_i);
                            for t=1:size(min_num,2)
                                if status{min_num(t),2}==temp_len
                                    status(min_num(t),:)=[];
                                    size_sta=size_sta-1;
                                end
                            end
                        end
                    end
                end
            end
                end
        end
    sta_len=zeros(1,size_sta);
        for q=1:size_sta
        sta_len(q)=status{q,2};
    end
    [max_len,max_lennum]=max(sta_len);
        disp('The char you need is: ')
    disp_max=status{max_lennum,4}(max_len:-1:1);
        disp(disp_max)
end

aysten

好了，现在http://aysten.3322.org/jisuan.asp可以用了。累死我了，一天一夜的工作啊~~~~~~~~~~

察看源文件可以看见里面的求解过程。

aysten

好长~~~
使用动态规划，看看我的参考答案吧：

算法分析：
求一个串的最长非升序子串，可以认为是反向的一个最长降序子串，由此定义函数f(n)为从左向右数第n个位置上的字符为头的最长非降序子串的长度，a(n)为第n个位置上的字符在字母表中的顺序，于是有递推关系：
            f(i)=max{ f(j)+1 | i<j , a(i)>=a(j) }   
这样我们应用动态规划算法就可以迅速求解了。程序在
http://aysten.3322.org/jisuan.asp 有演示
不过这也只是一种方法，也许还有更快的。

[此贴子已经被作者于2004-1-26 18:38:53编辑过]

itmwk

楼主,咋运行不了啊?

aysten

不好意思，这个asp我还是有些问题的，给你这个QB程序吧。
DECLARE FUNCTION solve$ (txt AS STRING)
DEFINT A-Z
DIM a AS STRING, b AS INTEGER
INPUT a
PRINT solve(a)
END

FUNCTION solve$ (txt AS STRING)
DIM a(1000), lnth, i, j, max, p(1000), mp, h AS STRING
lnth = LEN(txt)
FOR i = 1 TO lnth
FOR j = 1 TO i - 1
  IF MID$(txt, lnth - i + 1, 1) >= MID$(txt, lnth - j + 1, 1) AND a(i) < a(j) + 1 THEN a(i) = a(j) + 1: p(i) = j
NEXT
IF a(i) > max THEN max = a(i): mp = i
NEXT
i = mp: h = ""
DO
h = h + MID$(txt, lnth - i + 1, 1)
i = p(i)
LOOP UNTIL i = 0
solve$ = h
END FUNCTION
测试了，应该没有问题。Qb可以在这里下载
http://aysten.3322.org/tools/qbasic.rar