Нужно решить простейший пример

[geh]

Это не совсем так. Если взять достаточное количество оборотов цикла, то
это перекроет все мыслимые варианты (многократно перекроет). Вот вам
и 100% - ная гарантия!! Докажите, что это не так!

[kiv]

Source of the post
Это не совсем так. Если взять достаточное количество оборотов цикла, то
это перекроет все мыслимые варианты (многократно перекроет). Вот вам
и 100% - ная гарантия!! Докажите, что это не так!

Да что тут доказывать? Обычная теория вероятности... Вы никогда не получите 100% вероятности. Сколь угодно близко - да, но не 100. Причем эти "сколь угодно близко" будут получены за счет, как вы сами написали, многократного перекрытия, т.е. ужасно неэффективной программы.

Чтобы не быть голословным - давайте ваш исходник, лучше C/С++ или Pascal, и посмотрим

[geh]

Я перевел программу с Бейсика на Паскаль
вот она.

Код: Выбрать все

uses crt;
var
   a1,a2,a3,a4,a5,a6,a7,a8,a9:longint;
   b1,b2,b3,b4,b5,b6,b7,b8,b9:longint;
   i,s:longint;
begin
   clrscr;
   a1:=305;
   a2:=7723;
   a3:=3385;
   a4:=2932;
   a5:=5321;
   a6:=3778;
   a7:=1082;
   a8:=2369;
   a9:=9281;
   randomize;
   for i:=1 to 1000 do
      begin
          b1:=random(2);
          b2:=random(2);
          b3:=random(2);
          b4:=random(2);
          b5:=random(2);
          b6:=random(2);
          b7:=random(2);
          b8:=random(2);
          b9:=random(2);
          s:=a1*b1+a2*b2+a3*b3+a4*b4+a5*b5+a6*b6+a7*b7+a8*b8+a9*b9;
          if abs(s-24012)<10 then             write(s:6,a1*b1:5,a2*b2:5,a3*b3:5,a4*b4:5,a5*b5:5,a6*b6:5,a7*b7:5,a8*b8:5,a9*b9:5)      endend.

[kiv]

Ваши 1000 проб с большой вероятностью ВСЕ варианты не перебирают. Ниже дописанный ваш исходник - он перебирает из 512 вариантов только примерно 440...

Словом, пусть математики скажут веское слово с точными формулами, но экспериментально для 9 чисел вашим методом для полного перебора всех вариантов надо 4-5 тысяч проб (т.е. на порядок больше), для 12 чисел - уже около 30000 проб, для 14 чисел - просто не дождался такого момента...

Так что ваш метод, увы, не годится. На порядки медленнее, и абсолютно никакой гарантии...

Код: Выбрать все

uses crt;
var
a1,a2,a3,a4,a5,a6,a7,a8,a9:longint;
b1,b2,b3,b4,b5,b6,b7,b8,b9:longint;
i,s:longint;

var used: array[0..511] of Integer;



begin

for i := 0 to 511 do
begin
 used[i] := 0;
end;

clrscr;
a1:=305;
a2:=7723;
a3:=3385;
a4:=2932;
a5:=5321;
a6:=3771;
a7:=1082;
a8:=2369;
a9:=9281;
randomize;
for i:=1 to 1000 do
begin
b1:=random(2);
b2:=random(2);
b3:=random(2);
b4:=random(2);
b5:=random(2);
b6:=random(2);
b7:=random(2);
b8:=random(2);
b9:=random(2);

s:= (((((((b1*2+b2)*2+b3)*2+b4)*2+b5)*2+b6)*2+b7)*2+b8)*2+b9;
used[s] := 1;

s:=a1*b1+a2*b2+a3*b3+a4*b4+a5*b5+a6*b6+a7*b7+a8*b8+a9*b9;
if abs(s-24012)<10 then
write(s:6,a1*b1:5,a2*b2:5,a3*b3:5,a4*b4:5,a5*b5:5,a6*b6:5,a7*b7:5,a8*b8:5,a9*b9:
5)
end;

s:=0;
for i:=0 to 511 do
begin
 s := s + used[i];
end;

writeln('Used: ',s);

end.



[zykov]

Source of the post Это не совсем так. Если взять достаточное количество оборотов цикла, то это перекроет все мыслимые варианты (многократно перекроет). Вот вам
и 100% - ная гарантия!! Докажите, что это не так!

Тут Kiv прав. Сами посчитайте, сколько нужно итераций только чтобы один из 512 вариантов выпал с подавляющей вероятностью.
А нужно то вообще, чтобы каждый из 512 выпал почти наверняка. Для этого нужно очень много итераций. То есть такое решение, хотя в принципе и работает, но оно сильно не практично.

Source of the post Никогда ни в одной книге по алгоритмам и программированию не слышал о другом критерии, кроме как временная эффективность и использование памяти.

Причем тут книги? Я же про практику. При всём моём уважении (как правило Вы пишите интересные вещи), желание оптимизировать всё подряд смотрится нелепо (как в фильме, где Вицин ходил и ломиком всё вокруг отламывал). В данном случае, где нужен перебор 512 вариантов и сделать это нужно один раз, производительность - вообще не проблема. Даже скрипт на bash сделает это за приемлемое время.

[kiv]

Source of the post
Сами посчитайте, сколько нужно итераций только чтобы один из 512 вариантов выпал с подавляющей вероятностью.

Вспомнил наконец, это же "задача собирателя купонов" - в среднем надо случайных чисел, чтоб получить все n вариантов - и это в идеальном случае ( - сумма n членов гармонического ряда, ). Примерно, кстати, соответствует экспериментам - только вот если учесть неидеальность генератора псевдослучайных чисел, то очень запросто можно и нарваться...

Что до вашего возражения - то соглашусь, что для конкретно 511 вариантов можно даже генерацией 9! перестановок и суммированием первых чисел перестановки, например , но уже при 25-30 числах любая минимальная оптимизация будет иметь огромное значение...

[zam2]

Source of the post ...если учесть неидеальность генератора псевдослучайных чисел,

Какая-такая неидеальность генератора? Генератор дает последовательность псевдослучайных чисел длиной в свой период. Ни одно число не будет повторено и ни одно не будет пропущено. Вот только не понятно, зачем нужны псевдослучайные, когда подходят последовательные натуральные.

[kiv]

Source of the post

Source of the post ...если учесть неидеальность генератора псевдослучайных чисел,

Какая-такая неидеальность генератора? Генератор дает последовательность псевдослучайных чисел длиной в свой период.

И какой период "свой", вы проверяли? В конкретном генераторе? И как эта длина соотносится с длиной генерируемой битовой последовательности? Вот вам простейший пример - генератор, генерирующий все, но только поочередно - четное-нечетное. И все, в случае трехбитовых чисел вы будете получать только 5 и 2... Вот, например, такая неидеальность...

Вот очень конкретный пример. Скомпилируйте Visual C++ 2010 (или Open Watcom - похоже, генераторы одинаковые) и дождитесь, если сможете, генерации ВСЕХ чисел.

Можете поменять N на меньшее число, чтоб убедиться, что все работает

Сейчас писал, не стремясь к эффективности, но все равно работает достаточно быстро, чтоб понять...

Код: Выбрать все

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

const int N = 14;
const int COUNT = (1 << N);
bool inUse[COUNT] = { false };

bool all()
{
 for(int i = 0; i < COUNT; ++i)
 if (!inUse[i]) return false;
 return true;
}

int used()
{
 int sum = 0;
 for(int i = 0; i < COUNT; ++i)
 if (inUse[i]) sum++;
 return sum;
}


int main(int argc, const char * argv[])
{
 int count = 0;
 for(;;)
 {
 int val = 0;
 for(int i = 0; i < N; ++i)
 val = (val << 1) + (rand()%2);
 inUse[val] = true;
 ++count;
 if (all())
 {
 printf("Table is full, count = %d\n",count);
 return 0;
 }
 if (count % 10000 == 0)
 {
 printf("Step %7d, filled %6d\n",count,used());
 }
 }
}


[geh]

Если посмотреть на числа и сравнить с результатом, который мы должны получить,
то видно, что результат может быть достигнут если использовано минимум 4 числа
(кстати все 9 чисел разом нам тоже не нужны), так что реальных вариантов меньше 512
Тут уже предлагалось использовать натуральные числа. А действительно, нельзя ли
используя один цикл, задать в нем двоичное или иное число начиная с 100 (4 в двоичном виде)
и считать при каждом обороте цикла увеличивая его на 1.

[kiv]

Все, ухожу из темы, потому что тут собрались не читатели, а писатели...