Задача по программированию (длина цепочки нулей)
Среди публикаций на Infostart обнаружил следующую (. Среди приведенного автором списка задач есть такая:
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. Входные данные: последовательности нулей и единиц. Выходные данные: число (длина цепочки)
Автор предлагает вариант перебора входной строки. Как мне кажется, эта задача может быть решена значительно проще с помощью встроенных функций платформы.
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. Входные данные: последовательности нулей и единиц. Выходные данные: число (длина цепочки)
Автор предлагает вариант перебора входной строки. Как мне кажется, эта задача может быть решена значительно проще с помощью встроенных функций платформы.
По теме из базы знаний
Ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(1)
Как вариант так.
МассивСтрок = СтрРазделить(Строка, "1");
ТЗ = Новый ТаблицаЗначений;
ТЗ.Колонки.Добавить("Строки");
Для каждого ЭлементМассива из МассивСтрок Цикл
НоваяСтрока = ТЗ.Добавить();
НоваяСтрока.Строки = ЭлементМассива;
КонецЦикла;
//ТЗ.ЗагрузитьКолонку(МассивСтрок, "Строки");
Тз.Сортировать("Строки УБЫВ");
Сообщить("Максимальная длина непрерывной цепочки нулей - " + СтрДлина(ТЗ[0].Строки)); ПоказатьКак вариант так.
(13)
Синтаксис:
ЗагрузитьЗначения(<МассивЗначений>)
Параметры:
<МассивЗначений> (обязательный)
Тип: Массив.
Массив, содержащий значения для заполнения списка значений.
Описание:
Загружает список значений значениями из переданного массива. При этом все прежние элементы списка удаляются.
ЗагрузитьЗначения(<МассивЗначений>)
Параметры:
<МассивЗначений> (обязательный)
Тип: Массив.
Массив, содержащий значения для заполнения списка значений.
Описание:
Загружает список значений значениями из переданного массива. При этом все прежние элементы списка удаляются.
(14)
МассивСтрок = СтрРазделить(Строка, "1", Ложь);
СЗ = Новый СписокЗначений;
СЗ.ЗагрузитьЗначения(МассивСтрок);
СЗ.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
Сообщить("Максимальная длина непрерывной цепочки нулей - " + СтрДлина(СЗ[0].Значение));
(16) Это частный случай. А если задача будет найти не цепочку нулей, а самую длинную цепочку "без единиц"? Тогда будет работать и решение в (5). Оно всегда будет работать (особенно если вынести его в отдельную функцию, и передавать в параметр разделитель).
А твоё - не будет )))
А твоё - не будет )))
МаксимальнаяДлина = 0;
СтрокаНолейИЕдениц = "0100011100000011001";
МассивСтрок = СтрРазделить(СтрокаНолейИЕдениц, "1");
Для каждого ЗаписьСтрока Из МассивСтрок Цикл
Если МаксимальнаяДлина < СтрДлина(ЗаписьСтрока) Тогда
МаксимальнаяДлина = СтрДлина(ЗаписьСтрока)
КонецЕсли;
КонецЦикла; ПоказатьВхСтрока = "10010001010000101";
ВхМассив = СтрРазделить(ВхСтрока,"1");
СЗ = Новый СписокЗначений;
СЗ.ЗагрузитьЗначения(ВхМассив);
СЗ.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
Сообщить(СтрДлина(СЗ.Получить(0)));
Добавлю свой код.
Функция ЗадачаДлинаЦепочки(вхСтрока)
счетчик=0;
дСтроки=СтрДлина(вхСтрока);
маска="0";
пока истина цикл
приемник=СтрЗаменить(вхСтрока,маска,"");
если СтрДлина(приемник)=дСтроки тогда
прервать
конецесли;
счетчик=счетчик+1;
маска=маска+"0";
конеццикла;
возврат счетчик;
КонецФункции
Показать
(26) Мммм... Тогда мне интересно - в каком случае значение "дСтроки" станет равной значению СтрДлина(Приемник)?
Ведь "дСтроки" у нас - максимальная длина первоначальной вхСтрока, и нигде далее по циклу не изменяется.
А вот длина "приемника" - всегда уменьшается в цикле за счет увеличения "маски".
Таким образом я хочу понять - в каком случае сработает "Прервать"???
Ведь "дСтроки" у нас - максимальная длина первоначальной вхСтрока, и нигде далее по циклу не изменяется.
А вот длина "приемника" - всегда уменьшается в цикле за счет увеличения "маски".
Таким образом я хочу понять - в каком случае сработает "Прервать"???
(32)
когда после СтрЗаменить ничего не изменится в первоначальной строке.
А в цикле в СтрЗаменить передается нарастающая строка из нулей.
маска=маска+"0";
Как только цепочка нулей превысит существующую цепочку в первоисточнике, то и замены не произойдет. Вот и получится Макс длина такой цепочки (вычисленная на предыдущей итерации).
Таким образом я хочу понять - в каком случае сработает "Прервать"???
когда после СтрЗаменить ничего не изменится в первоначальной строке.
А в цикле в СтрЗаменить передается нарастающая строка из нулей.
маска=маска+"0";
Как только цепочка нулей превысит существующую цепочку в первоисточнике, то и замены не произойдет. Вот и получится Макс длина такой цепочки (вычисленная на предыдущей итерации).
(33)Как то так. (В первоначальном варианте была ошибка, исправил.)
Функция ЗадачаДлинаЦепочки(вхСтрока)
дСтроки=СтрДлина(вхСтрока);
маска="0";
приемник=СтрЗаменить(вхСтрока,маска,"");
счетчик=дСтроки-СтрДлина(приемник);
если счетчик <2 тогда
возврат счетчик;
конецесли;
для н=1 по счетчик цикл
маска=маска+"0";
конеццикла;
счетчик=счетчик+1;
пока истина цикл
приемник=СтрЗаменить(вхСтрока,маска,"");
если СтрДлина(приемник)<>дСтроки тогда
прервать
конецесли;
счетчик=счетчик-1;
маска=Лев(маска,счетчик);
конеццикла;
возврат счетчик;
КонецФункции
Показать
(37) По мне так еще хуже стало... Ты точно программист?
Пойду лучше коньяка выпью.
ВхСтрока = "000001111000101010101111110000";
дСтроки=СтрДлина(вхСтрока); // Получаем 30
Приемник=СтрЗаменить(вхСтрока,"0",""); // Получаем "11111111111111"
Счетчик=дСтроки-СтрДлина(приемник); // 30 - 14 = 16
//
для н=1 по счетчик цикл
маска=маска+"0";
конеццикла; // Добавляем к маске 16 нулей, и получаем маску(!!!) в семндацать(!) нулей.
//
пока истина цикл
приемник=СтрЗаменить(вхСтрока,маска,""); // То есть пытаемся найти в строке 17(!!!) нулей. Но их там нет.
если СтрДлина(приемник)<>дСтроки тогда // Никогда не равна. Длина входной строки 30, а приемника 16
прервать
конецесли;
счетчик=счетчик-1; // Счетчик стал 16
маска=Лев(маска,счетчик);
// А приёмник не изменился!!!
конеццикла;
ПоказатьПойду лучше коньяка выпью.
(37) Еще один способ, на случай если отберут СтрРазделить() или СтрЗаменить(). Для любителей пузырьков.
&НаКлиенте
Функция ЗадачаДлинаЦепочкиПоловинноеДеление(ВхСтрока)
ДлинаСтроки = СтрДлина(вхСтрока);
СтрокаИзНулей = СтрЗаменить(ВхСтрока, "1", "");
КоличествоНулей = СтрДлина(СтрокаИзНулей);
Маска = СтрокаИзНулей;
ИсходнаяСтрока = ВхСтрока;
Возврат ПроверитьВхождениеСтроки(Маска, КоличествоНулей)
КонецФункции
&НаКлиенте
Функция ПроверитьВхождениеСтроки(Маска, КоличествоНулей)
КоличествоИтераций = 1 + КоличествоИтераций;
ПозицияНуля = СтрНайти(ИсходнаяСтрока, Маска);
Если ПозицияНуля = 0 Тогда //не нашли, идем влево
КоличествоНулей = Окр(КоличествоНулей / 2);
Маска = Лев(СтрокаИзНулей, КоличествоНулей);
Возврат ПроверитьВхождениеСтроки(Маска, КоличествоНулей);
Иначе //нашли
Если СтрНайти(ИсходнаяСтрока, Маска + "0") = 0 Тогда //проверим что по маске в которой на один "0" больше нет
Возврат КоличествоНулей;
Иначе //нашли по маске в которой на один "0" больше
КоличествоНулей = КоличествоНулей + Окр(КоличествоНулей / 2); //идем вправо
Маска = Лев(СтрокаИзНулей, КоличествоНулей);
Возврат ПроверитьВхождениеСтроки(Маска, КоличествоНулей);
КонецЕсли;
КонецЕсли;
КонецФункции
Показать
(43) В первых релизах С++ был С и пара "++" )))
Но там все это можно было писать, и работало это быстро. Вот пример кода со "стрзаменить" - это постоянный обход массива, т.е. цикл в цикле. Кажется, что платформа делает это быстро, но если сравнить с простым проходом по двоичным данным, то последнее будет делать это за одну итерацию цикла, т.к. никто не знает, будет ли строка заканчиваться единицей. С друго стороны, если у нас длина максимальной последовательности нулей больше, чем остаток строки и мы встретили единицу, то цикл можно заканчивать.
Но там все это можно было писать, и работало это быстро. Вот пример кода со "стрзаменить" - это постоянный обход массива, т.е. цикл в цикле. Кажется, что платформа делает это быстро, но если сравнить с простым проходом по двоичным данным, то последнее будет делать это за одну итерацию цикла, т.к. никто не знает, будет ли строка заканчиваться единицей. С друго стороны, если у нас длина максимальной последовательности нулей больше, чем остаток строки и мы встретили единицу, то цикл можно заканчивать.
Фреккен Бок напекла на кухне плюшки.
И разложила их в 15 тарелок: в первую тарелку 1 плюшку, в вторую - 2 плюшки,... в 15-ю -15 плюшек.
Карлсон собрался их пи... воровать и таскать из кухни в спальню.
Условие: За один прилет в кухню Карслсон может взять плюшки "с любого количества тарелок", но с каждой выбранной тарелки можно взять только "одинаковое количество за один прилет". (нельзя с одной тарелки взять 2, а с другой -три).
Какие минимальное количество "прилетов" понадобиться Карлсону, чтобы стащить все плюшки?
Объяснить логику, привести конечную формулу.
Задача на программирование. 1С тут ни при чем. Но этот алгоритм вполне себе используется в прикладных задачах бизнеса.
(Если что - то конечную формулу можно выразить встроенными средствами 1С, но это не главное)
И разложила их в 15 тарелок: в первую тарелку 1 плюшку, в вторую - 2 плюшки,... в 15-ю -15 плюшек.
Карлсон собрался их пи... воровать и таскать из кухни в спальню.
Условие: За один прилет в кухню Карслсон может взять плюшки "с любого количества тарелок", но с каждой выбранной тарелки можно взять только "одинаковое количество за один прилет". (нельзя с одной тарелки взять 2, а с другой -три).
Какие минимальное количество "прилетов" понадобиться Карлсону, чтобы стащить все плюшки?
Объяснить логику, привести конечную формулу.
Задача на программирование. 1С тут ни при чем. Но этот алгоритм вполне себе используется в прикладных задачах бизнеса.
(Если что - то конечную формулу можно выразить встроенными средствами 1С, но это не главное)
Сделал сравнение двух алгоритмов. На тестовых данных ДлинаЦепочкиСтрЗаменить работает быстрее чем ДлинаЦепочкиСтрРазделить.
Функция ДлинаЦепочкиСтрРазделить(вхСтрока) экспорт
список=новый СписокЗначений;
список.ЗагрузитьЗначения(СтрРазделить(вхСтрока,"1"));
список.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
счетчик=СтрДлина(список.Получить(0));
возврат (счетчик);
КонецФункции
Функция ДлинаЦепочкиСтрЗаменить(вхСтрока)
дСтроки=СтрДлина(вхСтрока);
маска="0";
приемник=СтрЗаменить(вхСтрока,маска,"");
ЧислоЕдиниц=СтрДлина(приемник) ;
ЧислоНулей =дСтроки-СтрДлина(приемник);
если ЧислоНулей <2 тогда
возврат ЧислоНулей;
конецесли;
//минимальная длина цепочки
счетчик=(ЧислоНулей-ЧислоНулей%(ЧислоЕдиниц+1))/(ЧислоЕдиниц+1);
для н=1 по счетчик-1 цикл
маска=маска+"0";
конеццикла;
если счетчик=0 тогда
счетчик=1;
конецесли;
пока истина цикл
приемник=СтрЗаменить(вхСтрока,маска,"");
если СтрДлина(приемник)=дСтроки тогда
прервать
конецесли;
счетчик=счетчик+1;
маска=маска+"0";
конеццикла;
возврат счетчик-1;
КонецФункции
Функция ТестоваяСтрока(вхДлина)
ГСЧ = Новый ГенераторСлучайныхЧисел(ТекущаяУниверсальнаяДатаВМиллисекундах());
т="";
для н=1 по вхДлина цикл
т=т+ГСЧ.СлучайноеЧисло(0,1);
конеццикла;
возврат т;
КонецФункции
Функция ТестированиеАлгоритмов(вхДлина) экспорт
перем счетчик;
т=ТестоваяСтрока(вхДлина);
для каждого имя из СтрРазделить("ДлинаЦепочкиСтрЗаменить(т),ДлинаЦепочкиСтрРазделить(т)",",") цикл
старт=ТекущаяУниверсальнаяДатаВМиллисекундах();
Выполнить("счетчик="+имя);
сообщить("Результат "+счетчик+" "+имя+ " "+(ТекущаяУниверсальнаяДатаВМиллисекундах()-старт));
конеццикла;
КонецФункции
Показать
(58) потому что ГСЧ более менее равномерно получается распределить 0 и 1. Больших цепочек не получится.
Ну и СтрРазделить(вхСтрока,"1"). Тут более уместно не выбирать пустые значения.
Попробуйте такую строку:
Ее можно многократно размножить, для больших значений вычислений.
Ну и СтрРазделить(вхСтрока,"1"). Тут более уместно не выбирать пустые значения.
Попробуйте такую строку:
ТестСтрока = "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
|10000000000001
|10000000001
|111111111111111111111111111111111111111111111111111111111111 ПоказатьЕе можно многократно размножить, для больших значений вычислений.
(59)
Длина строки 934 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 517
Длина строки 934 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 686
Длина строки 1 868 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 1 096
Длина строки 1 868 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 1 366
Длина строки 3 736 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 2 282
Длина строки 3 736 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 2 716
Длина строки 934 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 517
Длина строки 934 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 686
Длина строки 1 868 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 1 096
Длина строки 1 868 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 1 366
Длина строки 3 736 000 Результат 105 ДлинаЦепочкиСтрЗаменить(т) 2 282
Длина строки 3 736 000 Результат 105 ДлинаЦепочкиСтрРазделить(т) 2 716
(62) еще раз.
СтрРазделить(вхСтрока,"1", Ложь)
И основное, ДлинаЦепочкиСтрЗаменить(т) будет не всегда выигрывать. Я привел пример.
Просто слабое место в ДлинаЦепочкиСтрРазделить(т) это использование списка значений и его сортировка. Когда цепочка будет большой, а количество таких цепочек будет немного, то ДлинаЦепочкиСтрЗаменить(т) существенно проигрывает.
СтрРазделить(вхСтрока,"1", Ложь)
И основное, ДлинаЦепочкиСтрЗаменить(т) будет не всегда выигрывать. Я привел пример.
Просто слабое место в ДлинаЦепочкиСтрРазделить(т) это использование списка значений и его сортировка. Когда цепочка будет большой, а количество таких цепочек будет немного, то ДлинаЦепочкиСтрЗаменить(т) существенно проигрывает.
(64)
Все верно, через Вычислить получается быстрее.
Длина строки 500 000 Результат 20 ДлинаЦепочкиСтрЗаменить(т) 192
Длина строки 500 000 Результат 20 ДлинаЦепочкиСтрРазделить(т) 352
Длина строки 500 000 Результат 20 ДлинаЦепочкиВычислить(т) 158
Цель обсуждения была найти новые алгоритмы, что и было достигнуто.
Все верно, через Вычислить получается быстрее.
Длина строки 500 000 Результат 20 ДлинаЦепочкиСтрЗаменить(т) 192
Длина строки 500 000 Результат 20 ДлинаЦепочкиСтрРазделить(т) 352
Длина строки 500 000 Результат 20 ДлинаЦепочкиВычислить(т) 158
Цель обсуждения была найти новые алгоритмы, что и было достигнуто.
(66) и вишенка на тортик... перебор в цикле быстрее всего :)
Результат для тех же 500 000 :
Результат для тех же 500 000 :
Функция ДлинаЦепочкиСтрРазделитьПеребор(вхСтрока)
Длина = 0;
ВхМассив = СтрРазделить(вхСтрока,"1", Ложь);
Для Каждого СтрМассива Из ВхМассив Цикл
Длина = Макс(Длина, СтрДлина(СтрМассива));
КонецЦикла;
Возврат Длина;
КонецФункции ПоказатьПрикрепленные файлы:
(68)
Проверьте, если не трудно?
P.S. Маленький плюс данного алгоритма - "ненужный" символ необязательно должен быть "1", он может быть любым, даже набором самых разных символов - будет найдена длина последовательности именно нулей.
перебор в цикле быстрее всего :)
Интересно, а что будет с быстродействием при тупой проверке каждого символа в строке, вообще без ее преобразования? То есть:
Функция ДлинаЦепочкиСтр(вхСтрока)
Длина = 0;
МаксДлина = 0;
Сч = СтрДлина(вхСтрока);
Пока Сч > 0 Цикл
Если Сред(вхСтрока,Сч,1) = "0" Тогда
Длина = Длина + 1;
Иначе
МаксДлина = Макс(МаксДлина, Длина);
Длина = 0;
КонецЕсли;
Сч = Сч - 1;
КонецЦикла;
Возврат МаксДлина;
КонецФункции ПоказатьP.S. Маленький плюс данного алгоритма - "ненужный" символ необязательно должен быть "1", он может быть любым, даже набором самых разных символов - будет найдена длина последовательности именно нулей.
(69)
весь код тестов тут приведен. можете сами проверить.
Результат 19 ДлинаЦепочкиСтрЗаменить(т) 237
Результат 19 ДлинаЦепочкиСтрРазделить(т) 308
Результат 19 ДлинаЦепочкиВычислить(т) 177
Результат 19 ДлинаЦепочкиСтрРазделитьПеребор(т) 140
Результат 19 ДлинаЦепочкиСтр(т) 794
Проверьте, если не трудно?
весь код тестов тут приведен. можете сами проверить.
Результат 19 ДлинаЦепочкиСтрЗаменить(т) 237
Результат 19 ДлинаЦепочкиСтрРазделить(т) 308
Результат 19 ДлинаЦепочкиВычислить(т) 177
Результат 19 ДлинаЦепочкиСтрРазделитьПеребор(т) 140
Результат 19 ДлинаЦепочкиСтр(т) 794
Задача с плюшками.
1. Шаг
Берем по одной плюшке - общее количество 1*15,
берем по 2 плюшке - общее количество 2*14
по 3 - 3*13 и т.д.
Общая формула x*(16-x). Максимум при x=8. Уносим 8^2 = 2^6 плюшки
2. Шаг
Остается следующий набор
0
1,2,3,4,5.6,7
1,2,3,4,5.6,7
Для последовательности 1,2,3,4,5,6,7 формула будет x*(8-x). Максимум при x=4. Уносим 2*4^2 =2^5 плюшек.
3. Шаг
Остается следующий набор
0,0
1,2,3,
1,2,3,
1,2,3,
1,2,3,
Теперь берем по 2 плюшке. Уносим 4 *2^2=2^4 плюшки
4. Шаг Остается 8 тарелок по одной плюшке . Забираем оставшееся 8*1=2^3
Проверяем.
Всего было 8*15=120
Забрали 2^6+2^5+2^4+2^3=8*(8+4+2+1)=8*15=120
1. Шаг
Берем по одной плюшке - общее количество 1*15,
берем по 2 плюшке - общее количество 2*14
по 3 - 3*13 и т.д.
Общая формула x*(16-x). Максимум при x=8. Уносим 8^2 = 2^6 плюшки
2. Шаг
Остается следующий набор
0
1,2,3,4,5.6,7
1,2,3,4,5.6,7
Для последовательности 1,2,3,4,5,6,7 формула будет x*(8-x). Максимум при x=4. Уносим 2*4^2 =2^5 плюшек.
3. Шаг
Остается следующий набор
0,0
1,2,3,
1,2,3,
1,2,3,
1,2,3,
Теперь берем по 2 плюшке. Уносим 4 *2^2=2^4 плюшки
4. Шаг Остается 8 тарелок по одной плюшке . Забираем оставшееся 8*1=2^3
Проверяем.
Всего было 8*15=120
Забрали 2^6+2^5+2^4+2^3=8*(8+4+2+1)=8*15=120
(50)
Для сравнения можно упростить алгоритм: создать строку из одних нулей, по длине равную обрабатываемой, и в цикле "откусывать" от нее по одному нолику до тех пор, пока СтрокаИзНулей не будет найдена в вхСтрока - элементарно, одна строка кода внутри цикла.
Вот только выполняться такой код может гораздо дольше предложенного в (49) - так, при длине исходной строки в 1024 символа сложный цикл с половинным делением выполнится максимум 10 раз, а "простой" - до 1023.
Усложнять - просто.
Упрощать - намного сложнее.
В данном случае усложнение кода дает дихотомия, но она же дает и эффективность (скорость выполнения).
Упрощать - намного сложнее.
Для сравнения можно упростить алгоритм: создать строку из одних нулей, по длине равную обрабатываемой, и в цикле "откусывать" от нее по одному нолику до тех пор, пока СтрокаИзНулей не будет найдена в вхСтрока - элементарно, одна строка кода внутри цикла.
Вот только выполняться такой код может гораздо дольше предложенного в (49) - так, при длине исходной строки в 1024 символа сложный цикл с половинным делением выполнится максимум 10 раз, а "простой" - до 1023.
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот