Chinaunix

标题: 字符串处理 [打印本页]
作者: WHITLACK    时间: 2009-01-16 12:59
标题: 字符串处理
目前已有一组数据，如 “1,5,6,8,9.4,12,25,36,53……”
要求在依次输入从1开始的任意一个数字时（连续的），打印出最大的那个值，
如输入 “1,5,6,8”时打印 “8”
  输入  “1,5,6,8,9.4,12,6”时打印 “12”（数字大小是连续的，虽然次序不是从小到大）
  输入  “1,5,9.4,12,25”时打印“error！”(中间少了数字6,8）

请问应该怎么做，小弟初学，请名位能多多指教，谢谢


--------------------------------------------------

问题补充：

不好意思，可能我表达的有些不清楚，就是说：

1、输入的字符串中的数字间是以逗号分割的
2、输入的字符串中的数字必须符合给定的数据的大小顺序，中间不能缺少数字，如“1，6，8"就不可以（中间没有5）
3、输入字符串中的数字先后顺序可以打乱，如“1，8，6，5”也可以，但是“1，8，5”就不可以


举几个例子：

  2. 1,5,6                        ------> 6
  3. 1,5,6,8                     ------> 8
  4. 1,6,5,8                     ------> 8
  5. 5,6,8                        ------> error
  6. 1,5,6,8,9.4,12,25,36------> 36
  7. 1,5,6,9.4,12,25,36   ------> error


复制代码




----------------------------------------------

我的问题其实很简单，表述起来比较麻烦

换一个方式：

现在有1岁、2岁，3岁，5岁，8岁 共5个小孩

我现在要给这几个小孩分糖吃

1、如果我把糖只分给1、2、3的小孩，这样就可以说我把糖分给了最大3岁的小孩
2、如果我把糖只分给1、2、3、5岁的小孩，这样就可以说我把糖分给了最大5岁的小孩
3、如果我把糖只分给1、2、8的小孩，这样就可以说我分糖的方法不对，8岁的都给了，3岁和5岁的却不给--->error
4、如果我把糖只分给2、3、5岁的小孩，这样就可以说我分糖的方法不对，1岁的小孩没给     ----->error

5、如果我把糖只分给2、3、1、5岁的小孩，这样就可以说我把糖分给了最大5岁的小孩

[ 本帖最后由 WHITLACK 于 2009-1-16 14:02 编辑 ]
作者: langue    时间: 2009-01-16 13:16
似乎这个算法的选择分支并不完整，什么时候该处理缺 8 的情况，什么时候不该处理？
作者: rt77789    时间: 2009-01-16 13:22
标题: 回复 #1 WHITLACK 的帖子
我没清楚你说的意思。。
作者: smartlinux    时间: 2009-01-16 13:26
就是看不懂啊。
作者: cookis    时间: 2009-01-16 13:29
输入一个就在你的列表里查一下，如果有，就存起来（并且记录当前最大值）否则error, 输入结束后，将刚才数值列表中的最大值打印出来。
作者: fera    时间: 2009-01-16 13:31
原帖由 smartlinux 于 2009-1-16 13:26 发表
就是看不懂啊。

我猜不到
标题跟内容也不符。
作者: bruceteen    时间: 2009-01-16 13:34
楞没看懂什么算 “error！”(中间少了数字8）
作者: cookis    时间: 2009-01-16 13:47
我日，居然这么多人连题都没看清！
作者: drowsyboy    时间: 2009-01-16 13:48
标题: 回复 #1 WHITLACK 的帖子
这个应该不难吧，一次接收输入，如果输入不再序列中，就出错（与当前序列中的对应需要的值相等），否则比较是不是比最大值大，如果是，则设为最大值。
作者: WHITLACK    时间: 2009-01-16 13:49
各位兄弟，对不起，刚才表达不请，抱歉，已经更新，不知现在如何
作者: WHITLACK    时间: 2009-01-16 13:51
原帖由 cookis 于 2009-1-16 13:29 发表
输入一个就在你的列表里查一下，如果有，就存起来（并且记录当前最大值）否则error, 输入结束后，将刚才数值列表中的最大值打印出来。



我还想确认，从最小值到最大值间没有漏掉给定数据中的数

比如1，5，6，12 但是中间没有8和9.4，我也要返回error
作者: hellioncu    时间: 2009-01-16 13:55
输入  “1,5,9.4,12,6”时打印 “12”，少了6、8不算错？
作者: WHITLACK    时间: 2009-01-16 14:03
原帖由 hellioncu 于 2009-1-16 13:55 发表
输入  “1,5,9.4,12,6”时打印 “12”，少了6、8不算错？



算的，刚才笔误，谢谢提醒
作者: Sorehead    时间: 2009-01-16 14:08
楞是看了半天才明白楼主意思，楼主这个表达可真不怎么样。

还有个问题，会有重复值吗？
作者: WHITLACK    时间: 2009-01-16 14:12
原帖由 Sorehead 于 2009-1-16 14:08 发表
楞是看了半天才明白楼主意思，楼主这个表达可真不怎么样。

还有个问题，会有重复值吗？



不会有重复值，如果输入有重复，就error好了
表达能力是不怎么样，呵呵
作者: lictans    时间: 2009-01-16 14:17
原始数据是排序好的数？
作者: Sorehead    时间: 2009-01-16 14:19
如果数据数量不多的话，就采用笨方法，使用字符串查找。首先得到数的个数，就可以确定初始序列字符串的结束位置，然后遍历输入序列中的数字，挨个在这段字符串中查找，一旦不存在，就输入error。同时用一个变量记录最大值即可。

如果数据量大的话，就把初始序列中前N个数字构建成一个二叉排序树或者平衡二叉树。
作者: WHITLACK    时间: 2009-01-16 14:33
标题: 回复 #17 Sorehead 的帖子
数据量不大，最多也就是不到15个数，大概方法我也知道
不过小弟C基础不好，兄弟能否给个例子？拜谢！
作者: mwishes    时间: 2009-01-16 15:16
有时间要求没? 如果没有应该不麻烦,算法复杂度O(N*M),如果有序,还可有优化下O(M * logN):
orig_array[N] = { 1, 5, 6, 8, 9.4, 12, 25, ... };
r_array[M] = { 1,5,6,8, ... };
mark = 0;
full = 0;
result = 0;
for (i = 0 upto M-1) {
  if ( (temp = look_for(r_array)) > mark ) {  /* look_for 找orig中的位置,返回数组下标 */
    full += temp - mark;
    mark = temp;
    result = r_array;
  } else {
     full--;  /* 确保r_array中不重复出现某个值, 如果重复出现请在上面的if中增加去除orig_array元素的部分 */
  }
}

if (full == 0) {
   return result;
} else {
   return "error";
}
作者: 太平绅士    时间: 2009-01-16 15:29
LZ说的是这个意思不？

  2. #include <vector>
  3. #include <algorithm>
  4. #include <stdio.h>


  7. int main(int argc, char **argv)
  8. {
  9.         int 所有小孩[ ] = { 7, 5, 6, 8, 94, 12, 25, 1, 36, 53 };
  10. #        define 所有小孩数        ( sizeof( 所有小孩 ) / sizeof( 所有小孩[ 0 ] ) )
  11.         std::sort( &所有小孩[0], &所有小孩[0] + 所有小孩数 );


  14.         int 本组小孩[ ] = {1, 5, 6, 7, 8, 12, 25 };
  15. #        define 本组小孩数        ( sizeof( 本组小孩 ) / sizeof( 本组小孩[ 0 ] ) )
  16.         std::sort( &本组小孩[0], &本组小孩[0] + 本组小孩数 );


  19.         if( !std::equal( &本组小孩[0], &本组小孩[0] + 本组小孩数, &所有小孩[0] ) )
  20.                 printf( "Error\n" );
  21.         else
  22.                 printf( "MAX: %d\n", 本组小孩[ 本组小孩数 - 1 ] );

  24.         return 0;
  25. }

复制代码
作者: mcemil    时间: 2009-01-16 16:38
这题蛮有意思。
既然没有重复，就用最简单的方法hash下。用表记录下每个数据的下标，比如
1,5,6,8,9.4,12,25,36,53
则
ind[5]=2,ind[8]=4.........

然后：

(1)循环读入数据，判断是否有重复，有则打印error,结束。
(2)取得输入数据在初始数据中下标的最大值和最小值, imax,imin, 以及输入数据的总个数n。
(3)判断imax-imin+1==n
(4)不相等，则打印error
(5）相等，则打印最大值

举例：
输入
1,5,9.4,12,25

imax=ind[25]=8
imin=ind[1]=1
n=6
imax-imin+1=8-1+1=8不等于6，出错


时间复杂度为O(n)



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2