Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / 1,2,3,5,6,7,8... преобразовать в 1-3,5-8... / 15 сообщений из 15, страница 1 из 1
12.09.2006, 15:09:17
    #33981211
risfek
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
привет!
примерчик красивый есть у кого-нибудь
...
Рейтинг: 0 / 0
12.09.2006, 15:45:19
    #33981364
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Представим, что это массив.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
/**
 *  Принимает на вход массив положительных целых чисел и возращает
 *  массив выбранных диапазонов: {1,2,3,5,6,7,8,9,10} -> {1,-3,2,5,-5,10}
 */
 public   int [] work ( int [] data) {
  ArrayList< int > result =  new  ArrayList< int >();
  // Помещаем в результат первый элемент
  result.add(data[ 0 ]);
  // Запоминаем первое число
   int  prevNum = data[ 0 ];

  // Счетчик элементов в диапазоне
   int  counter = - 1 ;
  /*
   *  Обрабатываем все элементы массива. Для каждого элемента
   *  смотрим его отличие от предыдущего. Если отличие равно 1, то
   *  пропускаем его. Если отличие больше единицы, то добавляем его
   *  в массив результата -1 и предыдущий элемент.
   */
   for  ( int  i =  1 ; i < result.size; i++){
   // Получаем очередной элемент
    int  currNum = data[i];
   
   /*
    * Смотрим, если разница больше единицы, значит мы вышли из одного
    * диапазона. Надо добавить в массив счетчик (не всегда) и добавить
    * последний элемент в диапазоне (предыдущий элемент).
    */
    if  ((currNum - prevNum) >  1 ) {
     // Смотрим, если в диапазоне больше одного элемента, то надо
     // добавить их количество в массив.
      if  (counter < - 1 )  {
       result.add(counter);
     }
     // Добавляем конец диапазона
     result.(prevNum);
     // Обнуляем счетчик (один элемент всегда есть в диапазоне)
     counter = - 1 ;
    }  else  {
     // Продолжается один диапазон, нужно увеличить количество его элементов
    counter--;
   }
   // Запонимаем очередной элемент, на следующей итерации - он предыдущий
   prevNum = currNum;
  }
  
  // Могли выйти из диапазона. Добавляем его количество элементов в нем и 
  // выходим
   if  (counter < - 1 ) {
   result.add(counter);
  } 
  // Добавляем последнее число - это конец диапазона
  result.add(currNum);
   return  result.toArray();
}

Я думаю как-то так можно. Кодировал без IDE, прямо здесь набирал код придумывая на ходу. Поэтому будем считать, что это псевдо-java.

А вообще, это лабораторная работа?
...
Рейтинг: 0 / 0
12.09.2006, 16:15:41
    #33981497
Penkov Vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
код сильно не читал, но сдается мне, он полагается на "корректность" входжных данных. а если их перемешать? то есть на вход идет 3 2 1 7 6 5
...
Рейтинг: 0 / 0
12.09.2006, 16:22:29
    #33981528
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
ArrayList.sort или что-то похожее есть в Collections Framework :)

А если серьезно, то все сильно зависит от структуры входных данных. Есть у меня пдозрение - тут можно сильно оптимизировать задачу при работе с большими данными за счет правильной структуры входных данных. Если же речь идет о страницах, которые на принтер выдаются - вполне достаточно и так :)
...
Рейтинг: 0 / 0
12.09.2006, 16:28:17
    #33981565
Penkov Vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
я предлагаю такой вариант. вводим структуру
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
 class  NumSet {
    private  Set< int > numbers;
    public  NumSet( int  a) {
       Set< int > num =  new  HashSet< int >();
       num.add(a);
        return   new  NumSet(num);
   }

    public  NumSet(Set< int > numbers) {
       this .numbers = numbers;
   }

    public   int  getMax() {
      //здесь возвращаем максимум и numbers
   }

    public   int  getMin() {
      //здесь возвращаем минимум и numbers
   }

    public   boolean  isIntersecting(NumSet a) {
       //здесь проверка того, являются ли множества пересекающимися или 
       //"стоящие рядом", т.е например {1, 2} и {3, 4, 5} стоят рядом
       //основанная на сравнениях getMin и getMax
   }

    public   void  consume(NumSet a) {
       numbers.addAll(a.getNumbers());
   }

    public  Set< int > getNumbers() {
        return  numbers;
   }
}

далее для каждого числа из входных данных создаем объект NumSet, а затем в цикле начинаем их скрещивать. Если объекты пересекаются или стоят рядом, то 2ой добавляем в 1ый (методом consume) и удаляем его. Если же на каком то шаге пересечений не будет - то ответ получен.
...
Рейтинг: 0 / 0
12.09.2006, 16:33:29
    #33981596
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
WITH t AS
  (SELECT ',8,1,2,3,5,6,7,' s FROM dual)
SELECT ltrim(sys_connect_by_path(num_range, ','), ',')
FROM   (SELECT MIN(num) || '-' || MAX(num) AS num_range
              ,row_number() over(ORDER BY MIN(num)) rn
              ,SUM( 1 ) over() cnt
        FROM   (SELECT to_number(substr(s,
                                        instr(s, ',',  1 , LEVEL) +  1 ,
                                        instr(s, ',',  1 , LEVEL +  1 ) -
                                        instr(s, ',',  1 , LEVEL) -  1 )) num
                FROM   t
                CONNECT BY LEVEL <= length(s) - length(REPLACE(s, ',', '')) +  1 
                ORDER  BY num)
        WHERE  num IS NOT NULL
        GROUP  BY num - rownum)
WHERE  rn = cnt
START  WITH rn =  1 
CONNECT BY PRIOR rn = rn -  1 ;

LTRIM(SYS_CONNECT_BY_PATH(NUM_
--------------------------------------------------------------------------------
 1 - 3 , 5 - 8 
...
Рейтинг: 0 / 0
12.09.2006, 16:38:58
    #33981620
Penkov Vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Timm

в биореактор , жывотное
...
Рейтинг: 0 / 0
12.09.2006, 17:00:05
    #33981711
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Deady Timm

в биореактор , жывотное
Учись четать!
risfekпривет!
примерчик красивый есть у кого-нибудь
...
Рейтинг: 0 / 0
12.09.2006, 17:06:58
    #33981736
Leonidv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Deadyя предлагаю такой вариант. вводим структуру

далее для каждого числа из входных данных создаем объект NumSet, а затем в цикле начинаем их скрещивать. Если объекты пересекаются или стоят рядом, то 2ой добавляем в 1ый (методом consume) и удаляем его. Если же на каком то шаге пересечений не будет - то ответ получен.

То есть так получаем:
Код: plaintext
1.
{1}, {6}, {2} , {7}, {3}, {8}, {9}

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
{1} скр {6}?
{1} скр {2} -> {1,2}
{1,2} скр {7}?
{1,2} скр {3} -> {1,2,3}
{6} скр {1,2,3}?  // это можно не делать, наверное
{6} скр {7} -> {6, 7}
{6, 7} скр {8} -> {6, 7, 8}
{6, 7, 8} скр {9} -> {6, 7, 8, 9}
На выходе два множества, как и хотелось. Забавно. Наверное еще можно так делать - если не скр, то правый аргумент выносит в список рабочих множеств. После этого очередной элемент скр со всеми множествами списка рабочих множеств. После того, как все элементы закончатся в базовом списке, надо также обработать список рабочих множеств. Тут рекурсией попахивает, или я не прав?
...
Рейтинг: 0 / 0
12.09.2006, 17:20:05
    #33981784
Penkov Vladimir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
не проверял, но думаю тут хватит 2ного цикла, как в пузырьке
...
Рейтинг: 0 / 0
12.09.2006, 18:32:50
    #33982081
NotGonnaGetUs
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Если уж хреначить ООП куда попало, то нужно это делать так, чтобы потом не было стыдно:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
 public   class  Ranges {
     private  ArrayList<Range> ranges =  new  ArrayList<Range>();

     public   void  AddValue( int  i) {
         int  index = Collections.binarySearch(ranges, i);
         if  (index <  0 ) {
             int  insertPosition = -index -  1 ;

            Range prevRange = getRange(insertPosition -  1 );
             boolean  isExpandPrev = prevRange !=  null  && i - prevRange.to ==  1 ;
             if  (isExpandPrev) {
                prevRange.to = i;
            }

            Range nextRange = getRange(insertPosition);
             boolean  isExpandNext = nextRange !=  null  && nextRange.from - i ==  1 ;
             if  (isExpandNext) {
                nextRange.from = i;
            }

             if  (!isExpandNext && !isExpandPrev) {
                ranges.add(insertPosition,  new  Range(i, i));
            }  else   if  (isExpandNext && isExpandPrev) {
                prevRange.to = nextRange.to;
                ranges.remove(insertPosition);
            }
        }
    }

     public  String toString() {
        StringBuilder sb =  new  StringBuilder();
         for  (Range r : ranges) {
            sb.append(r.toString()).append(", ");
        }
         if  (sb.length() >  0 ) {
             return  sb.substring( 0 , sb.length() - ", ".length());
        }
         return  "";
    }

     private  Range getRange( int  index) {
         return  index >=  0  && index < ranges.size() ? ranges.get(index) :  null ;
    }

     private   static   class  Range  implements  Comparable<Integer> {
         private   int  from;
         private   int  to;

         public  Range( int  from,  int  to) {
             this .to = to;
             this .from = from;
        }

         public   boolean  contains( int  i) {
             return  from <= i && to >= i;
        }

         public   int  compareTo(Integer integer) {
             if  (from > integer) {
                 return   1 ;
            }
             if  (to < integer) {
                 return  - 1 ;
            }
             return   0 ;
        }

         public  String toString() {
             return  from + (from == to ? "" : "-" + to);
        }
    }
}

О(n*logn).

При необходимости можно легким движением руки поправить алгоритм, чтобы получилось О(n) для случая, когда числа добавляются в порядке возрастания...
...
Рейтинг: 0 / 0
13.09.2006, 19:19:49
    #33985371
NotGonnaGetUs
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
Согласитесь, что круче ООП только яйца?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
 public  String toFormattedString( int [] integers) {
     if  (integers.length ==  0 ) {
         return  "";
    }
    Arrays.sort(integers);
     int  last = integers[ 0 ];
    StringBuilder sb =  new  StringBuilder(Integer.toString(last));
     for  ( int  current : integers) {
         if  (current != last) {
            sb.append("-").append(last -  1 ).append(", ").append(current);
        }
        last = current +  1 ;
    }
     return  sb.toString();
}
...
Рейтинг: 0 / 0
14.09.2006, 11:00:37
    #33986289
risfek
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
отключали сетку, извините.
наверно воспользуюсь тем, что NotGonnaGetUs написал.
ООП красиво, угрожающе много :)

у меня наваять получилось (в контексте задачи)

Всем спасибо!

String result="";
Object[] o = r.toArray();
for(int i = 0; i<o.length; i++){
int j=i;
while(j<o.length-1&&
(Math.abs(((KoTreeMap)o[j]).getInt("ZKM")-((KoTreeMap)o[j+1]).getInt("ZKM"))==1)
){ j++; }
if(i==j){
result+=((KoTreeMap)o ).getInt("ZKM");
} else {
result+=((KoTreeMap)o).getInt("ZKM")+ "-"+((KoTreeMap)o[j]).getInt("ZKM");
}
i=j;
result+=(i<o.length-1)?", ":"";
}
return result;
...
Рейтинг: 0 / 0
14.09.2006, 12:28:25
    #33986620
java != javaScript
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
2risfek:

1. 5(!) класс кастов.
2. Константа захардкоженная 5(!) раз.
3. Конкатенация String в цикле(!).
4. Изменение переменной цикла в теле цикла.
5. Вложенные циклы (while).
6. Отсутствие поясняющих комментариев.
7. Необходимость в комментариях (!) (как минимум описание входных данных, для которых алгоритм отработает корректно).

Не пиши так.
...
Рейтинг: 0 / 0
19.09.2006, 14:15:20
    #33996820
NotGonnaGetUs
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
1,2,3,5,6,7,8... преобразовать в 1-3,5-8...
java != javaScript
Не пиши так.

А так можно?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
(define (get-pairs numbers)
  (define (get-pair start current numbers)
    (cond ((null? numbers) (list (list start current)))
          (else (let ((next (+ current 1)))  
                  (cond ((= next (car numbers)) (get-pair start next (cdr numbers)))
                        (else (cons (list start current) (get-pairs numbers))))))))
  (cond ((null? numbers) ())
        (else (let ((start (car numbers)))
                (get-pair start start (cdr numbers)))))) 

Usage:
Код: plaintext
1.
2.
3.
(get-pairs '(1 2 3 5 7 10 11 12 16 17 18 19))
 
;output: ((1 3) (5 5) (7 7) (10 12) (16 19))
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / 1,2,3,5,6,7,8... преобразовать в 1-3,5-8... / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]