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

приведи ссылку на задачу, или укажи область значений N
...
Рейтинг: 0 / 0
12.12.2011, 11:00
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37570951
BeatCoder
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BeatCoder
Гость
Aleksandr Sharahov,
N(3<=N<=15), а S(|S|<10 8 )
...
Рейтинг: 0 / 0
12.12.2011, 14:26
| Ответить | Цитировать | Написать  
Расстановка знаков
    #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, 14:51
| Ответить | Цитировать | Написать  
Расстановка знаков
    #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:10
| Ответить | Цитировать | Написать  
Расстановка знаков
    #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:26
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37571094
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
PS. Среда - VBA MS Access 2003.
...
Рейтинг: 0 / 0
12.12.2011, 15:27
| Ответить | Цитировать | Написать  
Расстановка знаков
    #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, 16:28
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37571896
BeatCoder
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BeatCoder
Гость
Спасибо!
...
Рейтинг: 0 / 0
12.12.2011, 23:15
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37572013
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мне эта задача напоминает "Укладку Рюкзака"
...
Рейтинг: 0 / 0
13.12.2011, 01:15
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37572139
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Так это и есть вариация на тему задачи об одномерном рюкзаке...
...
Рейтинг: 0 / 0
13.12.2011, 08:45
| Ответить | Цитировать | Написать  
Расстановка знаков
    #37572965
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
BeatCoder,

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

Интересно, что эту задачу можно решить без внутреннего цикла
примерно в 2 раза быстрее, применяя для нумерации сумм коды Грея.
...
Рейтинг: 0 / 0
13.12.2011, 14:50
| Ответить | Цитировать | Написать  
13 сообщений из 13, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Расстановка знаков
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=37570951&tid=1342563]:
 0ms
get settings:
 9ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 147ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 62ms
get tp. blocked users:
 2ms
others: 215ms
total:  475ms
созд. / загр.: 475ms
x
x
Закрыть


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