Головоломка по программированию - Nalchik On Line - Форум Нальчика и КБР
Nalchik On Line - Форум Нальчика и КБР
Вернуться   Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing
Перезагрузить страницу Головоломка по программированию
Ответ
Опции темы
  (#1) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
Головоломка по программированию - 20.03.2012, 10:59

Может кто может помочь решить задачку школьную....

Есть вложенные циклы, максимальное вложение циклов 3000, для каждого цикла заданы начальное и конечное значения (шаг всегда 1). В самом последнем цикле стоит просто увеличение целой 32битной переменной i=i+1
Нужно вычислить i.
Загвоздка в том, что начальное значение любого из циклов может быть числом, а может текущим значением переменной вышестоящего цикла....
Максимальный объем памяти 64Мб, время работы менее 1 секунды....
Посетить домашнюю страницу ID_
Ответить с цитированием
  (#2) Непрочитано
Новичок
Аватар для Калай лама
Сообщений: 41
Регистрация: 23.01.2012
Адрес: Кашхатау
Возраст: 40
Репутация: 5 Рейтинг
20.03.2012, 12:48

ты хоть проц укажи тогда


Научитесь видеть разницу между человеком и его позицией по тому или иному вопросу. Атакуйте не человека, а вредоносные эмоции и конкретный тип поведения.
Посетить домашнюю страницу Калай лама
Ответить с цитированием
  (#3) Непрочитано
grand Master
Аватар для Leon
Сообщений: 1,055
Регистрация: 08.02.2007
Репутация: 47 Рейтинг
20.03.2012, 13:24

программно решаеться через рекурсию. Если надо вычеслить i, но при этом не используя i=i+1, то тебе нужно найти сумму шагов (конечное значение минус начальное), но тут надо чуть подумать и додуматься как это сделать без операции умножения, перемножать шаги циклов будет накладным, хотя хз
Ответить с цитированием
  (#4) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
20.03.2012, 18:22

Цитата:
Сообщение от Leon Посмотреть сообщение
программно решаеться через рекурсию. Если надо вычеслить i, но при этом не используя i=i+1, то тебе нужно найти сумму шагов (конечное значение минус начальное), но тут надо чуть подумать и додуматься как это сделать без операции умножения, перемножать шаги циклов будет накладным, хотя хз
Рекурсия это ясно, перемножить шаги цикла не проблема, проблема в том, что возможна вот такая штука
for( a=1; a<100; a++)
for(b=4; b<200; b++)
for(c=b; c<20; c++)
for(d=a; d<40; d++)
i=i+1;
и так до 3000.... сложность с последними двумя строками, они зависят от предыдущих циклов.... таких зависимостей может быть сколь угодно много.

Добавлено через 49 секунд
Цитата:
Сообщение от Калай лама Посмотреть сообщение
ты хоть проц укажи тогда
Да хоть самый мощный используй, только распаралеливать нельзя.... задача для школьников, они еще распаралеливать не могут

Последний раз редактировалось ID_; 20.03.2012 в 18:39.
Посетить домашнюю страницу ID_
Ответить с цитированием
  (#5) Непрочитано
grand Master
Аватар для Leon
Сообщений: 1,055
Регистрация: 08.02.2007
Репутация: 47 Рейтинг
20.03.2012, 19:29

зависимость границ ещё можно обдумать, а вот как c<20, d<40, с укозанием числом без переменной, вот тут проблема
Ответить с цитированием
  (#6) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
20.03.2012, 19:41

Цитата:
Сообщение от Leon Посмотреть сообщение
зависимость границ ещё можно обдумать, а вот как c<20, d<40, с укозанием числом без переменной, вот тут проблема
Да числа заданы, есть исходный файл данных который содержит
1 строка - количество циклов N
2 строка старт первого цикла, конец первого цикла
3 строка старт второго цикла, конец второго цикла
...
до N циклов

Если старт сикла отрицательное число, например -3, то это означает, что старт данного цикла это текущее значение цикла 3 по счету, т.е. для моего примера файл данных таков:
4
1 100
4 200
-2 20
-1 40
Циклов может быть до 3000, максимальное значение в каждом цикле 3000, наша переменная i может переполняться, это нормально.
Нужно сгенерировать выходной файл и туда эту i засунуть....

Последний раз редактировалось ID_; 20.03.2012 в 19:45.
Посетить домашнюю страницу ID_
Ответить с цитированием
  (#7) Непрочитано
grand Master
Аватар для Leon
Сообщений: 1,055
Регистрация: 08.02.2007
Репутация: 47 Рейтинг
20.03.2012, 19:41

for( a=1; a<100; a++, i++)
for(b=4; b<200; b++, i++)
for(c=b; c<20; c++, i++)
for(d=a; d<40; d++, i++)

это тоже самоё или есть преимущество в чём то?
Ответить с цитированием
  (#8) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
20.03.2012, 19:49

Цитата:
Сообщение от Leon Посмотреть сообщение
for( a=1; a<100; a++, i++)
for(b=4; b<200; b++, i++)
for(c=b; c<20; c++, i++)
for(d=a; d<40; d++, i++)

это тоже самоё или есть преимущество в чём то?
Нет, I++ только в последнем ибо даст лишние увеличения....
for(a=1; a<3; a++, i++)
for(b=1; b<4; b++, i++)
даст i=8
for(a=1; a<3; a++)
for(b=1; b<4; b++)
i++;
даст i=6
Посетить домашнюю страницу ID_
Ответить с цитированием
  (#9) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,487
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 36
Репутация: 32 Рейтинг
21.03.2012, 10:01

Читаешь файл в двумерный массив.
Пробегаешься по ячейкам, вытаскиваешь значение для цикла - запускаешь цикл и считаешь свою переменную.
Нашел число меньше нуля, вытащил из массива соответствующее значение и пошел снова считать.


"Mad girlfriend bug", is a bug whose immediate effect remains hidden - the app outwardly seems to function normally and tells you that everything is fine.
Ответить с цитированием
  (#10) Непрочитано
Новичок
Сообщений: 3
Регистрация: 21.03.2012
Репутация: 0 Рейтинг
21.03.2012, 10:35

такая программа вряд ли пройдет по времени, здесь нужно что-то более замысловатое, может даже какую-нибудь рекурсию применить,
Ответить с цитированием
  (#11) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,487
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 36
Репутация: 32 Рейтинг
21.03.2012, 10:54

Ну если не обязательно юзать вложенные циклы (не понятно из условия задачи), то можно тупо суммировать длину циклов. Так конечно быстрее будет.


"Mad girlfriend bug", is a bug whose immediate effect remains hidden - the app outwardly seems to function normally and tells you that everything is fine.
Ответить с цитированием
  (#12) Непрочитано
Крутой
Сообщений: 162
Регистрация: 19.12.2010
Адрес: Нальчик
Возраст: 28
Репутация: 1 Рейтинг
21.03.2012, 12:42

Цитата:
Если старт сикла отрицательное число, например -3, то это означает, что старт данного цикла это текущее значение цикла 3 по счету, т.е. для моего примера файл данных таков:
4
1 100
4 200
-2 20
-1 40
Циклов может быть до 3000, максимальное значение в каждом цикле 3000, наша переменная i может переполняться, это нормально.
Нужно сгенерировать выходной файл и туда эту i засунуть....
не понятно как быть в такой ситуации:
4
1 100 // 99
4 200 // 295
-2 20 // я правильно понял, тут получается 295 < 20 ?
-1 40 //
Ответить с цитированием
  (#13) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
21.03.2012, 13:51

Цитата:
Сообщение от Taktik Посмотреть сообщение
Цитата:
Если старт сикла отрицательное число, например -3, то это означает, что старт данного цикла это текущее значение цикла 3 по счету, т.е. для моего примера файл данных таков:
4
1 100
4 200
-2 20
-1 40
Циклов может быть до 3000, максимальное значение в каждом цикле 3000, наша переменная i может переполняться, это нормально.
Нужно сгенерировать выходной файл и туда эту i засунуть....
не понятно как быть в такой ситуации:
4
1 100 // 99
4 200 // 295
-2 20 // я правильно понял, тут получается 295 < 20 ?
-1 40 //
Нет -2 20 означает, что первый раз при b=4 цикл c от 4 до 19,
когда b=4, то цикл c от 5 до 19 и т.д.

Добавлено через 5 минут
Цитата:
Сообщение от DeadMeat Посмотреть сообщение
Читаешь файл в двумерный массив.
Пробегаешься по ячейкам, вытаскиваешь значение для цикла - запускаешь цикл и считаешь свою переменную.
Нашел число меньше нуля, вытащил из массива соответствующее значение и пошел снова считать.
при 3000 вложенных циклов где значения от 1-до максимум 3000 каждого цикла это сколько он считать будит?
Ничего не суммируется там, так как вложенные циклы могут зависеть от значения переменных вышестоящих циклов, а они могут например 3000 циклов где 3000й зависит от 2999, 2999 от 2998 и т.д. не пройдет по времени.

Последний раз редактировалось ID_; 21.03.2012 в 13:54.
Посетить домашнюю страницу ID_
Ответить с цитированием
  (#14) Непрочитано
Крутой
Сообщений: 162
Регистрация: 19.12.2010
Адрес: Нальчик
Возраст: 28
Репутация: 1 Рейтинг
21.03.2012, 13:57

Код:
for( a=1; a<100; a++)
     for(b=4; b<200; b++)
         for(c=b; c<20; c++)
              for(d=a; d<40; d++)
                   i=i+1;
если b>20 значение i не получим, так?
Ответить с цитированием
  (#15) Непрочитано
grand Master
Сообщений: 1,234
Регистрация: 31.05.2010
Репутация: 144 Рейтинг
21.03.2012, 14:00

Цитата:
Сообщение от Taktik Посмотреть сообщение
Код:
for( a=1; a<100; a++)
     for(b=4; b<200; b++)
         for(c=b; c<20; c++)
              for(d=a; d<40; d++)
                   i=i+1;
если b>20 значение i не получим, так?
Когда b>=20 циклы c переменными c и d не выполняются естественно, но это частный случай, программа то должна считать на любых значениях....
Посетить домашнюю страницу ID_
Ответить с цитированием
Ответ


Вернуться Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Германская головоломка Resnichka БеседКа 12 07.11.2013 17:58
Программированию в Linux Zalim2006 Developing 3 31.08.2010 18:41
Нужны услуги по программированию DOM, программатор типа Тритон First1728 Hardware 0 11.07.2010 19:08
Ищу учителя по программированию (PHP, Pascal) GaGaBoy Работа 40 05.05.2010 10:28
Преступление без наказания, головоломка. Хромой Флудилка 16 18.06.2009 08:32