Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Расстановка знаков / 13 сообщений из 13, страница 1 из 1
11.12.2011, 23:29
    #37570089
BeatCoder
BeatCoder
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Здравствуйте! Разбирая прошлогоднюю олимпиаду по программированию, я наткнулся на довольно интересную задачку: В строке записано N натуральных чисел. Сколько существуют способов расставить между ними знаки "+" и "-", чтобы получить число S. Всё бы ничего, но одно НО: время выполнения не более 2 сек.!! Если бы этого ограничения не было, я бы смог тупым подбором подобрать все необходимые варианты.
Так вот, не могли бы вы помочь начинающему программисту с логикой данной программы, я не прошу исходников, просто прошу помочь немного с алгоритмом.
Заранее благодарен!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 09:19
    #37570330
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Так это ж по определению полный перебор.
Видимая оптимизация - это пляски с хранением промежуточных результатов, вместо пересчёта выражения корректировать результат предыдущего.
Вторая видимая оптимизация - использования алгоритма построения корректировок, которая перебирает все варианты так, что каждый следующий отличается от предыдущего только на один элемент.
Что-то ещё придумать навскидку не удаётся...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 11:00
    #37570477
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoder,

приведи ссылку на задачу, или укажи область значений N
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 14:26
    #37570951
BeatCoder
BeatCoder
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Aleksandr Sharahov,
N(3<=N<=15), а S(|S|<10 8 )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 14:51
    #37571017
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoderAleksandr Sharahov,
N(3<=N<=15), а S(|S|<10 8 )

Всего 2^15=32768 вариантов расстановки знаков.
Просто цикл по i и xor с i-1, перекидывание знака у слагаемых.
При этом корректируем текущую сумму.
2 сек более, чем достаточно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 15:10
    #37571060
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoderAleksandr Sharahov,
N(3<=N<=15), а S(|S|<10 8 )

по-моему при таком раскладе обычный перебор уложится даже на самых давних системах (с частотой проца в 800-1000 MHz)...
Вообщем так... надо выполнить 2 N-1 проверок. Для одной проверки нам надо сложить(вычесть) N-1 чисел. Одна операция сложения/вычисления берёт 7 тактов (14 проверок = 98 тактов).
как написано в литературе один переход цикла - 16 тактов. Ну и сравнение - сколько-то там... ну например 10 тактов

тогда 98+16+10 = 124такта на один вариант... таких вариантов 2 14 =16384 ... итого в чистом виде нам потребуется около 2 миллиона тактов. ну пускай нам проц выделить 1% времени... + пускай половину тактов сожрёт компилятор на сервисные комманды и т.д. (то есть имеем 0.5% проц. времени).... получаем 800/200 = 4 миллиона тактов/сек. для нашей программы. То есть при самом худшем раскладе мы впишемся в 0.5 секунды (грубо, возможно неточно... но факт: времени для перебора придостаточно)

P.S. Если я неправ поправте пожалуйста ))) пробовал освоить данную тему как-то раньше... и вот не знаю правильно ли я считаю :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 15:26
    #37571091
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoderN(3<=N<=15), а S(|S|<10 8 )
Запустил поиск на Е2160 1.8 Ггц при N=15.
Время полного перебора вариантов - 0.045-0.063 сек.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 15:27
    #37571094
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
PS. Среда - VBA MS Access 2003.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 16:28
    #37571217
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoder,

практически любой современный процессор позволяет
менее чем за 0.5 сек перебрать все суммы 25 слагаемых:
Код: 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.
42.
43.
procedure TForm1.Button5Click(Sender: TObject);
var
  a: array of integer;
  i, j, m, last, k, n, delta, count: integer;
  t: dword;
begin;
  k:=9;                               //числа [0..k]
  n:=25;
  SetLength(a,1+n);
  a[0]:= - n * (k-2) div 2;            // -S
  for i:=1 to n do a[i]:=Random(k);    // числа
  //---------------------------------
  delta:=0;
  count:=0;
  for i:=0 to n do delta:=delta + a[i];
  if delta=0 then inc(count);
  Memo1.Lines.Clear;
  for i:=0 to n do Memo1.Lines.Add(IntToStr(a[i]));
  for i:=1 to n do a[i]:=2 * a[i];
  t:=GetTickCount;
  //----------------------------------
  last:=1 shl n - 1;
  j:=0;
  repeat;
    m:=j;
    j:=j+1;
    m:=m xor j;
    i:=n;
    repeat;
      if m and 1<>0 then begin;
        a[i]:=-a[i];
        delta:=delta+a[i];
        end;
      m:=m shr 1;
      dec(i);
      until m=0;
    if delta=0 then inc(count);
    until j=last;
  //----------------------------------
  t:=GetTickCount-t;
  Memo1.Lines.Add(IntToStr(count)+' вариантов');
  Memo1.Lines.Add(IntToStr(t)+' мсек');
  end;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.12.2011, 23:15
    #37571896
BeatCoder
BeatCoder
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.12.2011, 01:15
    #37572013
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Мне эта задача напоминает "Укладку Рюкзака"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.12.2011, 08:45
    #37572139
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
Так это и есть вариация на тему задачи об одномерном рюкзаке...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.12.2011, 14:50
    #37572965
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстановка знаков
BeatCoder,

В качестве упражнения:

Интересно, что эту задачу можно решить без внутреннего цикла
примерно в 2 раза быстрее, применяя для нумерации сумм коды Грея.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Расстановка знаков / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 552ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1342563]:
 0ms
get settings:
 10ms
get forum list:
 21ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 198ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 63ms
get tp. blocked users:
 1ms
others: 235ms
total:  552ms
x
x
Закрыть


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