Переключение на Главную Страницу Страницы: 1 ОтправитьПечать
Обычная тема Нужен алгоритм (число прочтений - 2510 )
ev-kov
God Member
*****
Отсутствует



Сообщений: 694
Зарегистрирован: 27. Декабря 2006
Пол: Мужской
Нужен алгоритм
06. Февраля 2008 :: 08:21
Печать  
Есть набор целых чисел например : 1,2,3,4,6,7,8,9,11,14,15,16,17 на выходе должно получиться 1-4,6-9,11,14-17
Пробовал сам, но что то где то не доглядел не всегда корректно он отрабатывает.
  

Информация - то, что снижает неопределенность в какой-либо области и очень важно не ошибиться областью в наш информационный век!
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #1 - 06. Февраля 2008 :: 08:36
Печать  
Я примерно такое делал через ИТЗ и его метод Группировать (пусть даже автору ИТЗ этот метод не нравится, а я от него балдею  Подмигивание )
в общем, если поймёшь что-нибудь, то держи:
Код
Выбрать все
Функция СформироватьДиапазонНомеров(Знач ТзИтзЗапрос
	, ИмяСтолбцаНачало="Начало" //имя колонки в выходной таблице, которая будет содержать первый номер серии
	, ИмяСтолбцаКонец="Конец"//имя колонки в выходной таблице, которая будет содержать последний номер серии
	, ИмяСтолбцаКоличество="Количество" //можно через зпт (суммируемые показатели)
	, ИмяСтолбцаНомер="Номер"//имя колонки вх. таблице по которым строится серии
	, ИмяСтобцаТипВид="Тип" //можно через зпт (колонки группировки)
	, ИмяКолонкиДопГруппировки="" //ПЕРВИЧНАЯ группировка, основное будет в тзПотомки
	)

	Перем КопияИТ;//:ИндексированнаяТаблица
	Перем спГруппировок;//:СписокЗначений
	итВых = СоздатьОбъект("ИндексированнаяТаблица");
	ВходнойТип = ТипЗначенияСтр(ТзИтзЗапрос);
	Если ВходнойТип="ИндексированнаяТаблица" Тогда
		итВых.Загрузить(ТзИтзЗапрос);
	ИначеЕсли ВходнойТип="Запрос" Тогда
		итВых.ЗагрузитьЗапрос(ТзИтзЗапрос,1,0);
	ИначеЕсли ВходнойТип="ТаблицаЗначений" Тогда
		итВых = ТзИтзЗапрос.Копия();
	Иначе
		Сообщить("Можно передавать только ТЗ, ИТЗ или Запрос","!");
		Возврат "";
	КонецЕсли;

	спГруппировок = СписокИзСтрокиСРазделителями(ИмяСтобцаТипВид); 	КолГруппировок=спГруппировок.РазмерСписка();

	ИмяИндекса=ИмяСтобцаТипВид+ИмяСтолбцаНомер; КолонкиИндекса="*"+СтрЗаменить(ИмяСтобцаТипВид, ",", ",*")+","+ИмяСтолбцаНомер;
	Попытка	итВых.УдалитьКолонку(ИмяСтолбцаНачало);
	Исключение	КонецПопытки;
	Попытка	итВых.УдалитьКолонку(ИмяСтолбцаКонец);
	Исключение	КонецПопытки;
	итВых.НоваяКолонка(ИмяСтолбцаНачало);
	итВых.НоваяКолонка(ИмяСтолбцаКонец);
	итВых.ДобавитьИндекс(ИмяИндекса, КолонкиИндекса);
	КопияИТ = итВых.Копия(1);

	КлючМин = СоздатьОбъект("СписокЗначений");
	КлючМакс = СоздатьОбъект("СписокЗначений");
	КонНомер=0; НачНомер=0;
	КопияИТ.ВыбратьСтроки(ИмяИндекса);
	Пока КопияИТ.ПолучитьСтроку(ИмяИндекса) = 1 Цикл
		текНомер = КопияИТ.ПолучитьЗначение(,ИмяСтолбцаНомер);
		Если (текНомер>=НачНомер) и (текНомер<=КонНомер) и (НачНомер<>0)  Тогда Продолжить;	КонецЕсли;
		НачНомер = текНомер;
		КонНомер = НачНомер;
		Для й=1 По КолГруппировок Цикл
			КлючМин.ВставитьЗначение(й, КопияИТ.ПолучитьЗначение(,спГруппировок.ПолучитьЗначение(й)));
		КонецЦикла;
		КлючМин.ВставитьЗначение(КолГруппировок+1, НачНомер);
		КлючМин.Выгрузить(КлючМакс);
		Пока итВых.НайтиСтроку(ИмяИндекса, КлючМакс)<>0 Цикл
			КонНомер=КонНомер+1; КлючМакс.ВставитьЗначение(КолГруппировок+1, КонНомер);
		КонецЦикла;
		КонНомер=КонНомер-1;
		КлючМакс.ВставитьЗначение(КолГруппировок+1, КонНомер);
		итВых.УстановитьФильтр(КлючМин, КлючМакс, ИмяИндекса);
		итВых.ЗаполнитьКолонку(ИмяИндекса, ИмяСтолбцаНачало, НачНомер);
		итВых.ЗаполнитьКолонку(ИмяИндекса, ИмяСтолбцаКонец, КонНомер);
	КонецЦикла;

	ИндексГруппировки=ИмяСтолбцаНачало+ИмяСтолбцаКонец+СтрЗаменить(ИмяСтобцаТипВид, ",", "");
	стрДопГруппировка="";
	Если ПустаяСтрока(ИмяКолонкиДопГруппировки)=0 Тогда
		стрДопГруппировка=СтрЗаменить(ИмяСтобцаТипВид, ",", "")+":"+"*"+СтрЗаменить(ИмяКолонкиДопГруппировки, ",", ",*")+";";
	КонецЕсли;
	ИмяСтолбцаКонец+",*"+СтрЗаменить(ИмяСтобцаТипВид, ",", ",*")
					, ИмяСтолбцаКоличество, 1);

	//итВых.Показать();
	Возврат итВых;
КонецФункции 

  
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #2 - 06. Февраля 2008 :: 08:42
Печать  
Т.е. у меня на входе были таблицы с колонками "ТипБСО", "НомерБСО", "НачОст", "КонОст", "Приход", "Расход"
И надо было сделать серии по "НомеруБСО", но различая "ТипБСО"
вызываем эту ф-ию:

Код
Выбрать все
НоваяТЗ = СформироватьДиапазонНомеров(тзВхода, , ,
	, ИмяСтолбцаКоличество="НачОст, КонОст,Приход,Расход"
	, ИмяСтолбцаНомер="НомерБСО"
	, ИмяСтобцаТипВид="ТипБСО"
	)
 


на выходе будем иметь ИТЗ с колонками:
"ТипБСО", "Начало", "Конец", "НачОст", "КонОст", "Приход", "Расход" , "тзПотомки"
в тзПотомки хранятся строки исходной ТЗ
  
Наверх
 
IP записан
 
Thor
Junior Member
**
Отсутствует


I Love YaBB 2!

Сообщений: 82
Зарегистрирован: 12. Июля 2006
Re: Нужен алгоритм
Ответ #3 - 06. Февраля 2008 :: 08:59
Печать  
Что-то типа такого (если критерий интервала - последовательно идущие по возрастанию целые числа)
Код
Выбрать все
Процедура ЗаполнитьИзСтроки(тзЧисла, Стр)
	сз = СоздатьОбъект("СписокЗначений");
	сз.ИзСтрокиСРазделителями(Стр);

	Для инд = 1 По сз.РазмерСписка() Цикл
		тзЧисла.НоваяСтрока();
		тзЧисла.Число = сз.ПолучитьЗначение(инд);
	КонецЦикла;
КонецПроцедуры

//*******************************************
Процедура Сформировать()

	Перем тзЧисла, тзИнтервалы;

	тзЧисла = СоздатьОбъект("ТаблицаЗначений");
	тзЧисла.НоваяКолонка("Число", "Число", 10, 0);

	тзИнтервалы = СоздатьОбъект("ТаблицаЗначений");
	тзИнтервалы.НоваяКолонка("НачИнтервала", "Число", 10, 0);
	тзИнтервалы.НоваяКолонка("КонИнтервала", "Число", 10, 0);

	// загоняем числа в таблицу
	ЗаполнитьИзСтроки(тзЧисла, "1,2,3,4,6,7,8,9,11,14,15,16,17,19,30,41,1,2");

	КвоСтрок = тзЧисла.КоличествоСтрок();
	ПредыдущееЧисло = 0;
	НачИнтервала = 0;
	тзЧисла.ВыбратьСтроки();
	Пока тзЧисла.ПолучитьСтроку() = 1 Цикл
		Если тзЧисла.НомерСтроки = 1 Тогда
			НачИнтервала = тзЧисла.Число;
		ИначеЕсли тзЧисла.НомерСтроки = КвоСтрок Тогда
			тзИнтервалы.НоваяСтрока();
			тзИнтервалы.НачИнтервала = НачИнтервала;
			тзИнтервалы.КонИнтервала = тзЧисла.Число;
		Иначе
			Если (ПредыдущееЧисло+1) <> тзЧисла.Число Тогда
				тзИнтервалы.НоваяСтрока();
				тзИнтервалы.НачИнтервала = НачИнтервала;
				тзИнтервалы.КонИнтервала = ПредыдущееЧисло;

				НачИнтервала = тзЧисла.Число;
			КонецЕсли;
		КонецЕсли;

		ПредыдущееЧисло = тзЧисла.Число;
	КонецЦикла;

	тзИнтервалы.ВыбратьСтроки();
	Пока тзИнтервалы.ПолучитьСтроку() = 1 Цикл
		Если тзИнтервалы.НачИнтервала = тзИнтервалы.КонИнтервала Тогда
			Сообщить(""+тзИнтервалы.НачИнтервала);
		Иначе
			Сообщить(""+тзИнтервалы.НачИнтервала+"-"+тзИнтервалы.КонИнтервала);
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры
 

  
Наверх
ICQ  
IP записан
 
ev-kov
God Member
*****
Отсутствует



Сообщений: 694
Зарегистрирован: 27. Декабря 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #4 - 06. Февраля 2008 :: 09:00
Печать  
2 JohnyDeath гляну, на вскидку, очень заморочено.

Для сравнения у меня так сейчас, но надо отловить глюк и исправить алгоритм

Код
Выбрать все
Функция Преобразовать(Стр)
	Рез = "";
	Список = глРазложить(Стр);
	ПредыдущееЗнач = 0; НачБлока = 0; К = Список.РазмерСписка(); ДлинаБлока = 0; ПредНачБлока = -1;
	Для сч = 1 По К Цикл
		ТекЗнач = Число(Список.ПолучитьЗначение(сч));
		Если ПредНачБлока <> НачБлока Тогда
			НачБлока = ТекЗнач;
			ПредНачБлока = НачБлока;
			Рез = Рез + ?(Рез="",НачБлока,"")
		КонецЕсли;

		//НачБлока = ?(НачБлока = 0 ,ТекЗнач,НачБлока);
		Разница = ТекЗнач - ПредыдущееЗнач;
		Если (Разница > 1)и(ПредыдущееЗнач > 0) Тогда
			КонецБлока = ПредыдущееЗнач;
			//ДлинаБлока=ДлинаБлока+1;
			Рез = Рез + ?(ДлинаБлока > 2,"-"+ПредыдущееЗнач,""); //+ ?(ДлинаБлока > 2,,"");
			Рез = Рез + "," +ТекЗнач;
			НачБлока = ТекЗнач;
			ДлинаБлока = 0;
		ИначеЕсли Разница = 1 Тогда
			ДлинаБлока = ДлинаБлока + 1;
		КонецЕсли;

		Если сч = К Тогда
			ДлинаБлока = ?(К = 1,0,ДлинаБлока);
			Если ДлинаБлока = 1 Тогда
				Рез = Рез + ?(Рез="","",",") + ТекЗнач;
			ИначеЕсли ДлинаБлока > 1 Тогда
				Рез = Рез + ?(Рез="","","-") + ТекЗнач;
			КонецЕсли;
		КонецЕсли;
		ПредыдущееЗнач = ТекЗнач;
	КонецЦикла;
	Возврат Рез;
КонецФункции
 

  

Информация - то, что снижает неопределенность в какой-либо области и очень важно не ошибиться областью в наш информационный век!
Наверх
 
IP записан
 
ev-kov
God Member
*****
Отсутствует



Сообщений: 694
Зарегистрирован: 27. Декабря 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #5 - 06. Февраля 2008 :: 09:04
Печать  
Thor

Спасибо, то что надо
  

Информация - то, что снижает неопределенность в какой-либо области и очень важно не ошибиться областью в наш информационный век!
Наверх
 
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #6 - 06. Февраля 2008 :: 09:06
Печать  
ev-kov писал(а) 06. Февраля 2008 :: 09:00:
2 JohnyDeath гляну, на вскидку, очень заморочено.

В моей задаче нужно было отлавливать серии не по всей колонке целиком, а разделять их по др. колонкам (в примере по "ТипБСО") и таких колонок может быть несколько. Наверное, отсюда и заморочки... пока ничего лучшего не придумал, хотя переписываю этот алгоритм периодически  Очень довольный
  
Наверх
 
IP записан
 
Igor-bts
Full Member
***
Отсутствует


I Love YaBB 2!

Сообщений: 103
Зарегистрирован: 14. Июля 2006
Re: Нужен алгоритм
Ответ #7 - 06. Февраля 2008 :: 09:13
Печать  
Ну и я до кучи Улыбка)
Алгоритм тот же, перебор Улыбка


Процедура ЗаполнитьТаблицуПростыхЧисел()
     НачЗначения.НоваяКолонка("Номер","Число");
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 1;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 2;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 3;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 4;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 6;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 7;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 11;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 13;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 14;
     
     НачЗначения.НоваяСтрока();
     НачЗначения.Номер = 17;
     
     Диапазоны.НоваяКолонка("ДиапазонСтарт","Число");
     Диапазоны.НоваяКолонка("ДиапазонСтоп","Число");
КонецПроцедуры


Процедура Сформировать()
     Перем Итератор;
     ЗаполнитьТаблицуПростыхЧисел(); // первоначальное
     Итератор=0;
     НачЗначения.Сортировать("Номер");
     НачЗначения.ВыбратьСтроки();
     Пока НачЗначения.ПолучитьСтроку() = 1 Цикл
           Если Не(Итератор=НачЗначения.Номер) Тогда
                 Диапазоны.НоваяСтрока();
                 Диапазоны.ДиапазонСтарт= НачЗначения.Номер;
                 Итератор = НачЗначения.Номер;
           КонецЕсли;
           Диапазоны.ДиапазонСтоп = НачЗначения.Номер;
           Итератор = Итератор+1;
     КонецЦикла;
КонецПроцедуры
  
Наверх
ICQ  
IP записан
 
ev-kov
God Member
*****
Отсутствует



Сообщений: 694
Зарегистрирован: 27. Декабря 2006
Пол: Мужской
Re: Нужен алгоритм
Ответ #8 - 06. Февраля 2008 :: 09:42
Печать  
Igor-bts Самый короткий алгоритм!
  

Информация - то, что снижает неопределенность в какой-либо области и очень важно не ошибиться областью в наш информационный век!
Наверх
 
IP записан
 
kms
1c++ power user
1c++ moderator
Отсутствует


я хочу, чтоб сюда проложили
дорогу оттуда...

Сообщений: 4632
Зарегистрирован: 19. Мая 2006
Re: Нужен алгоритм
Ответ #9 - 06. Февраля 2008 :: 13:16
Печать  
В принципе, в дополнение в линейному поиску можно применить бинарный поиск, ибо массив сортированный.
Правда, реализация будет явно сложнее, чем у победителя соревнований, а по эффективности - бабушка надвое сказала (зависит от распределения данных).

По затратам (условно):

Линейный поиск: worst = O(n); best = O(n)
Бинарный поиск: worst < O(n*log(n)); best = O(log(n))

Т.е. если массив не состоит из нескольких длинных цепочек, заморачиваться не стоит.
  

De quelle planète es-tu?
Наверх
 
IP записан
 
Переключение на Главную Страницу Страницы: 1
ОтправитьПечать