ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм группировки последовательности чисел
6 сообщений из 6, страница 1 из 1
алгоритм группировки последовательности чисел
    #37489841
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
abc_da
Гость
Добрый день, хочу попросить у вас совета в решении следующей задачи:
Имеем последовательность целых чисел > 0, упорядоченную по-возрастанию, например:
3, 4, 5, 8, 9, 11, 12, 13, 14, 25

Необходимо записать последовательность в сокращенном виде, заменив все цепочки чисел, идущих по порядку в виде нижняя_граница-верхняя_границу.

Для приведенного примера результат должен выглядеть следующим образом:
3-5, 8, 9, 11-14, 25

Поделитесь, пожалуйста, своим видением оптимального алгоритма для реализации данной операции, мне в голову не приходит ничего лучше последовательного перебора-перебора-перебора, но формализовать не удается.

Заранее спасибо.
...
Рейтинг: 0 / 0
20.10.2011, 00:44
| Ответить | Цитировать | Написать  
алгоритм группировки последовательности чисел
    #37489843
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
abc_da
Гость
забыл добавить, все числа встречаются только 1 раз.
...
Рейтинг: 0 / 0
20.10.2011, 00:48
| Ответить | Цитировать | Написать  
алгоритм группировки последовательности чисел
    #37489849
Гата Селов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гата Селов
Участник
один проход. Запоминать число. Сравнивать число со следующим. Если следующее != текущее + 1, то вот она цепочка - от запомненного до текущего. Запомненное перезаписать следующим и далее как раньше.
...
Рейтинг: 0 / 0
20.10.2011, 01:07
| Ответить | Цитировать | Написать  
алгоритм группировки последовательности чисел
    #37489850
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
предыдущее число = - 1 
блок_чисел = пустой блок

цикл по всем числам
  если очередное_число > предыдущее_число+ 1  то
    если блок_чисел не пуст то напечатать блок_чисел
    блок_чисел.старт = очередное_число
  иначе 
    блок_чисел.конец = очередное_число
повторить
А теперь напильник в руки и вперед.
...
Рейтинг: 0 / 0
20.10.2011, 01:10
| Ответить | Цитировать | Написать  
алгоритм группировки последовательности чисел
    #37489897
abc_da
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
abc_da
Гость
Спасибо за помощь, вот, что у меня вышло:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
		 int  first = - 1 , last = - 1 ;		
		StringBuilder sb =  new  StringBuilder();

		 for ( int  i =  0 ; i < nums.length; i++) {
			 if (first == - 1 ) {
				first = nums[i];
			}  else  {
				last = nums[i];
			}
			
			 if (nums.length != i+ 1  && nums[i+ 1 ] - nums[i] ==  1 ) { // цепочка продолжается
				 continue ;
			}  else  { // цепочка оборвалась
				sb.append(join(first,last)); // выводим
				 if (nums.length != i+ 1 )	sb.append(", ");// если элемент не последний, добавляем запятую
				first = last = - 1 ;
			}
		}

Если кому интересно, в приложенном файле реализация на java
...
Рейтинг: 0 / 0
20.10.2011, 03:09
| Ответить | Цитировать | Написать  
алгоритм группировки последовательности чисел
    #37491093
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
abc_daСпасибо за помощь, вот, что у меня вышло:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
		 int  first = - 1 , last = - 1 ;		
		StringBuilder sb =  new  StringBuilder();

		 for ( int  i =  0 ; i < nums.length; i++) {
			 if (first == - 1 ) {
				first = nums[i];
			}  else  {
				last = nums[i];
			}
			
			 if (nums.length != i+ 1  && nums[i+ 1 ] - nums[i] ==  1 ) { // цепочка продолжается
				 continue ;
			}  else  { // цепочка оборвалась
				sb.append(join(first,last)); // выводим
				 if (nums.length != i+ 1 )	sb.append(", ");// если элемент не последний, добавляем запятую
				first = last = - 1 ;
			}
		}

Если кому интересно, в приложенном файле реализация на java
Несколько мыслей.

1) Мне кажется StringBuilder не нужен. Можно на ходу формировать System.out.
Это даст возможность обработать последовательности бесконечно большие.

2) Заглядывание вперёд ( nums[i+1] ) это дурной тон. Мне кажется если
этот конечный автомат адаптировать под обращение только к nums[i]
алгоритм станет более концептуальным. И также можно поточно
читать исходные данные через System.in
...
Рейтинг: 0 / 0
20.10.2011, 17:29
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм группировки последовательности чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=78&tid=1342665]:
 0ms
get settings:
 9ms
get forum list:
 23ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 63ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 36ms
get tp. blocked users:
 1ms
others: 247ms
total:  399ms
созд. / загр.: 399ms
x
x
Закрыть


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