Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 10

помогите оптимизировать программу. Не проходит тест, из-за большого количества используемой памяти.

28.11.2012, 22:11. Показов 1366. Ответов 12
Метки нет (Все метки)

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

Суть программы:

Есть последовательность чисел, в которой цифры каждого числа идут по возрастанию. То есть, 123456-подходит, 145-подходит, числа от 1 до 9 подходят, НО 34256-не подходит, 101-не подходит. В файле skaitli.in(текстовом). записано одно число. Это число является порядковым номером последовательности. В файл skaitli.out(текстовый) надо записать число, которое будет соответствовать данному номеру. Порядковый номер-n 1≤n≤2147483647.

Код:

Pascal
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
program skaitli;
var coun,coun1:longint;
     res:cardinal;
     num1,num2,teco:shortint;
     re:string;
     f:text;
     len:shortint;
begin
  coun1:=9; //номер последовательности(счетчик).
  res:=9;     //результат
  assign(f,'skaitli.in');
  reset(f);
  read(f,re);  //вытаскиваем порядковый номер из файла
  val(re,coun);  //вытаскиваем порядковый номер из строки
  close(f);
  teco:=0;
  if coun>9 then begin //числа от одного до 9 сразу являются результатом
  repeat
    inc(res);
    inc(coun1);
    repeat
      inc(teco); 
      repeat
        str(res,re);
        len:=length(re); //десятки
        val(re[teco],num1);
        val(re[teco+1],num2);
        if num1>num2 then begin //вытаскиваем из одного числа две рядом стоящие цифры и сравниваем (в зависимости 
          inc(res);                     //от кол-ва десятков в числе, проводится соответствующее кол-во операций).
        end;
      until num1<=num2;
    until len-1=teco;
    teco:=0;  //обнуляем счетчик
  until coun1=coun;
  end
  else res:=coun;
  assign(f,'skaitli.out');
  rewrite(f);
  write(f,res);
  close(f);
end.
Добавлено через 2 минуты
за "цифры по возрастанию" также принимаются одинаковые цифры. К примеру 111,122.

Добавлено через 35 минут
Народ! Ну не проходите мимо плз!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
28.11.2012, 22:11
Ответы с готовыми решениями:

Автоматизировать и оптимизировать обработку большого количества данных
Есть два файла, в одном случае только форма которую надо заполнить (фаил перечень) и есть заполненная таблица (фаил список) Ребята, кому не...

Можно ли оптимизировать функцию обработки большого количества строк
Всем привет... нужна ваша помощь. Есть функция, ей передается строка запроса к базе данных, она возвращает результат выполнения данного...

Выделение большого количества оперативной памяти
Я уже год разрабатываю свою игру на C# и только спустя это время, когда программа уже имеет довольно большой объём, я столкнулся с...

12
 Аватар для HighPredator
6045 / 2160 / 753
Регистрация: 10.12.2010
Сообщений: 6,005
Записей в блоге: 3
28.11.2012, 22:25
Приведите полный текст задачи. А то из того, что написано, ничего не понятно.
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 10
29.11.2012, 20:52  [ТС]
Молодой математический исcследователь Бетти исследует свойства прогрессивных чисел. В ее исследовании, прогрессивными называют такие числа, цифры которых, создают возрастающую последовательность. Например, 333 и 55788 являются прогрессивными числами, а 9123 и 3331 ими не являются.
Среди натуральных чисел, Бетти нашла много прогрессивных. Она дала каждому числу номер.
Бетти хочет проверить точность ее работы и попросить программистов назвать n-ое число.

Примеры текстовых файлов(вводные, выводные данные):

skaitli.in
5
skaitli.out
5


skaitli.in
18
skaitli.out
19

Вводные данные (skaitli.in):
В первом ряду, в текстовом файле дано n (1≤n≤2147483647).

Выводные данные (skaitli.out):
Вывести одно число, значение n-ого числа.

Примечание от меня:
1. Числа пронумерованы по возрастанию.
2. Если кто не знает:
Цифры-это состовляющие числа(1,2,3,4...).
Числа-это комбинации цифр(212,350,231).
0
73 / 72 / 37
Регистрация: 21.11.2009
Сообщений: 258
30.11.2012, 01:31
kolobok1, на неё тесты есть, чтобы проверить?

Добавлено через 6 минут
---
И цифры все-таки возрастающую последовательность образуют, или неубывающую?
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 10
02.12.2012, 00:55  [ТС]
p@$#@, Неубывающую, неубывающую.))
К сожалению, тестов нету. Все, что есть, я написал в условии.
0
181 / 179 / 23
Регистрация: 29.08.2012
Сообщений: 489
02.12.2012, 03:06
Может в корне поменять подход к решению? Не тупо перебирать все числа и проверять в них каждую пару циферок? Может надо основать алгоритм на том, что можно заранее сказать сколько прогрессивных чисел присутствует от 1 до заданного числа?
Проверь какой ценой ты используешь процедуру val() - сколько памяти это отжирает. Ты же активно её используешь...
1
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 10
02.12.2012, 03:45  [ТС]
Я пытался сделать программу, которая переберает по две цифры, в которой результат это тип стринг, но как то ничего не получилось(уж больно мудрено реализование функции inc для стринга). Пробовал написать без стринга вообще , чтобы не жралась память на Val и Str, но опять же ничего не вышло, так как не сумел придумать как разделять число на десятки без стринга.
Yurek, так ведь сказать сколько от первого до заданного числа последовательных чисел можно, это дано в файле. Меня де спрашивают какое конкретно число находится под данным номером.

Добавлено через 11 минут
Вот более менее улучшенная версия программы. Изза того, что мне не даны тесты на такие вводные данные как максимальное значение лонгинта, я не могу быть уверен, что программа работает 100 процентно корректно.
P.S. Про максимальное значение лонгинта я, конечно, выпендрился. Моя программа слишком тормознута, чтоб такие числа считать, хоть и должна!!!

Pascal
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
program skaitli;
var coun,coun1:longint;
    res:cardinal;
    re:string;
    f:text;
    len:shortint;
begin
  coun1:=9;
  res:=9;
  assign(f,'skaitli.in');
  reset(f);
  read(f,re);
  val(re,coun);
  close(f);
  if coun>9 then begin
  repeat
    inc(res);
    inc(coun1);
    str(res,re);
    len:=length(re);
    repeat
      dec(len);
      if re[len]>re[len+1] then begin
        inc(res);
        str(res,re);
        len:=length(re);
      end;
    until len=1;
  until coun1=coun;
  end
  else res:=coun;
  assign(f,'skaitli.out');
  rewrite(f);
  write(f,res);
  close(f);
end.
0
181 / 179 / 23
Регистрация: 29.08.2012
Сообщений: 489
02.12.2012, 14:25
Цитата Сообщение от kolobok1 Посмотреть сообщение
Меня де спрашивают какое конкретно число находится под данным номером.
Верно, но для этого тебе приходится перебрать все числа и посчитать прогрессивные. Когда счётчик прогрессивных докручивается до указанного тебе номера расчёт завершён, не так ли?
я не могу быть уверен, что программа работает 100 процентно корректно.
Тебе без тестов скажу, что она работает некорректно Она отрабатывает то, что требуется в задании, но не совсем. При малых значениях n (номер прогрессивного числа) она будет считать как положено - докрутит до соответствующего номера и выдаст значение числа. Коллизия состоит в том, что прогрессивных чисел в диапазоне от 1 до https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{31} намного меньше, чем всех чисел в диапазоне. Поэтому заранее можно сказать, что даже работая с диапазоном до https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{32} его не хватит чтобы добраться до прогрессивного числа с номером https://www.cyberforum.ru/cgi-bin/latex.cgi?n={2}^{31}.
Это является подсказкой, что алгоритм должен быть иным. Возможно разработчик задачи хотел чтобы решающий встретился с подобной сложностью и не шёл по пути простого перебора чисел, а если шёл, то придумал бы как обойти ограничения размерности. Хотя второе наверняка потребует бОльших ресурсов, так что лучше смотреть в сторону других вариантов.
P.S. Про максимальное значение лонгинта я, конечно, выпендрился. Моя программа слишком тормознута, чтоб такие числа считать, хоть и должна!!!
Да нет, она вполне может посчитать прогрессивные числа до https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{31} или даже https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{32} (не вникал точно до какого), вот только n при этом не выйдет за диапазон 100к Представляешь какие числа потребуются чтобы найти прогрессивное с номером https://www.cyberforum.ru/cgi-bin/latex.cgi?n={2}^{31} и сколько времени это считать? Кстати, у тебя не производится проверка превышения предела размерности, так что остановка с ошибкой неизбежна. Возможно когда ты будешь сдавать задачу в тот сервис, то вылезет другая проблема - превышение времени вычислений
0
 Аватар для агерон
447 / 300 / 65
Регистрация: 12.10.2009
Сообщений: 1,162
02.12.2012, 23:50
эх студенты.... держи и учись
Pascal
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
var number,countNumber, selectNumber:longint;
    didgit,oldDidgit:integer;
    flagNumber:boolean;
    f:text;
begin
 assign(f,'scaitli.in');
 reset(f);
 read(f,countNumber);
 close(f);
 while (countNumber>0) do
  begin
   inc(number);
   flagNumber:=false;
   oldDidgit:=-1;
   selectNumber:=number;
   while (selectNumber>0) do
    begin
     didgit:=selectNumber mod 10;
     selectNumber:=selectNumber div 10;
     if oldDidgit=-1 then
      begin
       oldDidgit:=didgit;
       continue;
      end;
     if didgit<=oldDidgit then
      oldDidgit:=didgit
     else
      begin
       flagNumber:=false;
       break;
      end;
     flagNumber:=true;
    end;
   if flagNumber then dec(countNumber);
  end;
 assign(f,'scaitli.out');
 rewrite(f);
 write(f,number);
 close(f);
end.
1
181 / 179 / 23
Регистрация: 29.08.2012
Сообщений: 489
03.12.2012, 10:31
В первой сотне вроде должно быть 54 прогрессивных числа. По Вашей программе получается 45. Не может ли быть, что забыты числа из первой десятки от 1 до 9-ти ?
И мне кажется, автору хотелось самому решить и требовалась только подсказка, а теперь у него и стимула не будет рыпаться

PS. Опять же, остаётся решить проблему превышения размерности переменных.
0
 Аватар для агерон
447 / 300 / 65
Регистрация: 12.10.2009
Сообщений: 1,162
03.12.2012, 16:40
я считал что прогрессивные числа состоят из 2 и больше цифр, ну... если бы он хотел сам решить эту задачу то он бы над ней бился пока не нашел бы корректное решение, а тут явно видно что он хочет просто пройти тест, задача не сложна но посути просто нужно взглянуть под другим углом на проблему сравнения цифр числа, может в будущем он вспомнит как я реализовал эту задачу и не будет решать свои тесты грубой силой в лоб
0
181 / 179 / 23
Регистрация: 29.08.2012
Сообщений: 489
03.12.2012, 18:51
Цитата Сообщение от агерон Посмотреть сообщение
я считал что прогрессивные числа состоят из 2 и больше цифр
Да я тоже как бы был в сомнениях, но он привёл результат тестов:
skaitli.in
5
skaitli.out
5
...может в будущем он вспомнит как я реализовал эту задачу и не будет решать свои тесты грубой силой в лоб...
Да просто в виде спойлера можно сделать - чтобы код не было видно, но можно было подглядеть, если совсем невмоготу
0
73 / 72 / 37
Регистрация: 21.11.2009
Сообщений: 258
06.12.2012, 21:57
Вот тут выше говорят про подсказку... Скажем так, даже проверка на прогрессивность за O(1), перебирая все числа не будет работать, ибо это не проходит по ограничениям. Тут хитрее надо .

Если ещё непонятно как делать...
Динамикой, обыкновенной динамикой... не сильно сложной. К сожалению, пишу с чужого компьютера, поэтому код показать не могу. Если не догадаетесь, напишу более подробно суть решения
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.12.2012, 21:57
Помогаю со студенческими работами здесь

Загрузка и отображение большого количества картинок с памяти телефона
Если изображения больше 10, то начинаются заметные тормоза, если больше 100, то программа падает с ошибкой памяти у меня есть массив,...

Очистка памяти при генерации большого количества чисел в ListBox
Пишу сейчас псевдогенератор случайных чисел по алгоритму линейного сопоставления.. При генерации 9000000 чисел в ListBox прога сьедает...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru