ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
25 сообщений из 339, страница 7 из 14
  7  все
Относительно простые задачки
    #39924707
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
Имя пользователя1
labarad,

В худших случаях по прежнему 5*N, хотя таких кейсов намного меньше

Надо будет преодолеть лень и самому попробовать модифицировать код, чтобы получить практический результат. Исхожу из предположения, что число переходов может сократиться с 4N до 2N для больших N:
1N - последовательно по кругу от нуля к нулю +
1N - возврат к голове.

Но даже в этом (худшем) случае оптимизация с 4N до 3N - это 25%-ый прирост производительности и стоит прилагаемых усилий.

Худший случай: каждый следующий ноль находится на расстоянии большем (x+1), чем путь (x) от первичной точки до текущего нуля.

Единственный вопрос: стоит ли считать операцию сравнения как дополнительную, сравнимую с переходом из вагона в вагон?
...
Рейтинг: 0 / 0
10.02.2020, 15:36
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39924930
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
Имя пользователя1,

Поразмыслил более предметно. Вынужден согласиться с Вашей оценкой в 5N. 2N добавляет финальная проверка на хвост (голову).
...
Рейтинг: 0 / 0
10.02.2020, 20:34
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39926025
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
К задаче классификации натуральных на (х 2*х 3*х ... К*х).
Сделал проверку для К=10(только) можно экспериментировать с подбором к-тов (правда универсальную для лбого К делать это долго и муторно, но нарастить довольно быстро, ну и МЛ никого не заинтересует)
 
Код: java
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.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
  %%%%%%%%  запускать  clear all; close all; row= 1; my10_mod;
K=10; pk=4; T=K^pk;   N= cast([0:T-1]', 'int32');
KI(1, :)= [1, 1, 1, 1];  %% double
KI(2, :)= [1, 4, 6, 9];
KI(3, :)= [0, 4, 6, 9];  %% error "+1"
KI(4, :)= [1, 0, 6, 9];  %% error "+1"
KI(5, :)= [1, 4, 0, 9];  %% error "+1"
KI(6, :)= [1, 4, 6, 0];  %% error "+1"
KI(7, :)= [1, 1, 1, 0];  %% error "+1"
KI(8, :)= [0, 1, 0, 1];  %% error "+1+1"
KI(9, :)= [3 9 3 9] .* KI(1, :);
ki= KI(row, :)'; 
    
%% Вычислить массив по форуле
S= sprintf( '%04.0i', N); ... %% здесь 4==pk
S(S==' ')= '0'; ...
S= reshape(S, pk, [])'; ... %% матрица(T*pk) цифр (для K<11)
D4= reshape( sscanf(S, '%1i'), T, []); clear S; ... %% матрица(T*pk) всех вычетов
M(1:T)= mod( D4*ki, K); ... %% формула классификации
    

%% Проверка
... h1= [1000, 100, 10, 1]; h2= 2*h1; h3= 3*h1; 
h1= zeros(1,pk); h1(pk)=1; for t= pk:-1:2  h1(t-1)= floor(K*h1(t));  end;
h2= 2*h1; h3= 3*h1;

  %{
   M(1+0+h1(1)+h1(3))= M(1+0);  % имитация ошибочной формулы (нек-х повторов)
   M(1+8070+h1(1)+h1(3))= M(1+8070); 
   M(1+6060+h1(1)+h1(3))= M(1+6060); 
  %}

V2357= zeros(T,pk);  V2= zeros(T, pk);  V2325= zeros(T, pk);
 %% hk= 1 + mod(i+h1(:), T);
for i1= (0:K-1)
  for i2= (0:K-1)
    for i3= (0:K-1)
      for i4= (0:K-1)
        ij= [i1, i2, i3, i4]; ij0= 1+ij*h1';
        ij1= mod(1+ij, K); ij2= mod(2+ij, K); ij3= mod(3+ij, K); 
        J= logical([1 1]); ij23= zeros(1,pk); ij23(J)= mod(1+ij(J), K);
        J= logical([1 0 1]); ij25= zeros(1,pk); ij25(J)= mod(1+ij(J), K);

  %% I= (M(ij)==M(ij+"1000"));
  H1= [ij; ij; ij; ij]; x= diag(ones(pk,1)); H1(logical(x))= ij1';  
  Y= M(1+H1*h1'); 
  I= (M(ij0)==Y)';  V2357( 1+ ij*h1', I)= 1;

  H22= ij; H22(1)= ij2(1);  if M(ij0)==M(1+H22*h1')  V2(ij0, 1)= 1; end;  %%"2^2"
  H23= ij; H23(1)= ij3(1);  if M(ij0)==M(1+H23*h1')  V2(ij0, 2)= 1; end;  %%"2^3"
  H32= ij; H32(2)= ij2(2);  if M(ij0)==M(1+H32*h1')  V2(ij0, 3)= 1; end;  %%"3^2"
 ...
  H223= ij; H223(1)= ij1(1);  H223(2)= ij1(2);  if M(ij0)==M(1+H223*h1')  V2325(ij0, 1)= 1; end; %%"2*3"
  H225= ij; H225(1)= ij1(1);  H225(3)= ij1(3);  if M(ij0)==M(1+H225*h1')  V2325(ij0, 2)= 1; end; %%"2*5"

        end;
    end;
  end;
end;


%% Проверка проверок
[sum(V2357); sum(V2); sum(V2325)]
% z=find(V2357(:,4)~=0); size(z), D4(z(1:3), :), M(z(1:3)),

...
Рейтинг: 0 / 0
12.02.2020, 22:19
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39926307
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Немного подрихтовал, чтобы можно было безболезненно проверять комбинации для К=[7; 10]. Вроде менял только вот это:
 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
  %%%%%%%%  запускать  clear all; close all; row= 1; my10_mod;
.....   
%% Вычислить массив по форуле
S= sprintf( '%04.0i', N); ... %% здесь 4==pk
S(S==' ')= '0'; ...
S= reshape(S, pk, [])'; ... %% матрица(T*pk) цифр (для K<11)
D4= reshape( sscanf(S, '%1i'), T, []); clear S; ... %% матрица(T*pk) всех вычетов
M(1:T)= mod( D4*ki, K); ... %% формула классификации

снова полный вариант:
 
Код: java
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.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
  %%%%%%%%  запускать  clear all; close all; row= 1; K=10; my10_mod;
pk=4; T=K^pk;   N= cast([0:T-1]', 'int32');
KI(1, :)= [1, 1, 1, 1];  %% double
KI(2, :)= [1, 4, 6, 9];
KI(3, :)= [0, 4, 6, 9];  %% error "+1"
KI(4, :)= [1, 0, 6, 9];  %% error "+1"
KI(5, :)= [1, 4, 0, 9];  %% error "+1"
KI(6, :)= [1, 4, 6, 0];  %% error "+1"
KI(7, :)= [1, 1, 1, 0];  %% error "+1"
KI(8, :)= [0, 1, 0, 1];  %% error "+1+1"
KI(9, :)= [3 9 3 9] .* KI(1, :);
KI(10, :)= [1 2 3 1] .* KI(1, :);
KI(11, :)= [2 2 3 1] .* KI(1, :);
KI(12, :)= [2 2 2 2] .* KI(1, :);  %% error для 10, 8 (но не для 9, 7)
KI(13, :)= 5* KI(1, :);
ki= KI(row, :)'; 
    
%% Вычислить массив по форуле
... h1= [1000, 100, 10, 1]; h2= 2*h1; h3= 3*h1; 
h1= zeros(1,pk); h1(pk)=1; for t= pk:-1:2  h1(t-1)= floor(K*h1(t));  end;
D4= zeros(T, pk); ... %% матрица(T*pk) всех вычетов
for i1= (0:K-1)
  for i2= (0:K-1)
    for i3= (0:K-1)
      for i4= (0:K-1)
        ij= [i1, i2, i3, i4]; ij0= ij*h1'; 
        N(1+ij0)= ij0;  D4(1+ij0, :)= ij;
      end;
    end;
  end;
end;
N= cast(N, 'int32');
M(1:T)= mod( D4*ki, K); ... %% формула классификации
    

%% Проверка
... h1= [1000, 100, 10, 1]; h2= 2*h1; h3= 3*h1; 
h1= zeros(1,pk); h1(pk)=1; for t= pk:-1:2  h1(t-1)= floor(K*h1(t));  end;
h2= 2*h1; h3= 3*h1; h4= 4*h1; ...

  %{
   M(1+0+h1(1)+h1(3))= M(1+0);  % имитация ошибочной формулы (нек-х повторов)
   M(1+8070+h1(1)+h1(3))= M(1+8070); 
   M(1+6060+h1(1)+h1(3))= M(1+6060); 
  %}

V2357= zeros(T,pk);  V2= zeros(T, pk);  V2325= zeros(T, pk);
 %% hk= 1 + mod(i+h1(:), T);
for i1= (0:K-1)
  for i2= (0:K-1)
    for i3= (0:K-1)
      for i4= (0:K-1)
        ij= [i1, i2, i3, i4]; ij0= 1+ij*h1';
        ij1= mod(1+ij, K); ij2= mod(2+ij, K); ij3= mod(3+ij, K); 
        J= logical([1 1]); ij23= zeros(1,pk); ij23(J)= mod(1+ij(J), K);
        J= logical([1 0 1]); ij25= zeros(1,pk); ij25(J)= mod(1+ij(J), K);

  %% I= (M(ij)==M(ij+"1000"));
  H1= [ij; ij; ij; ij]; x= diag(ones(pk,1)); H1(logical(x))= ij1';  
  Y= M(1+H1*h1'); 
  I= (M(ij0)==Y)';  V2357( 1+ ij*h1', I)= 1;

  H22= ij; H22(1)= ij2(1);  if M(ij0)==M(1+H22*h1')  V2(ij0, 1)= 1; end;  %%"2^2"
  H23= ij; H23(1)= ij3(1);  if M(ij0)==M(1+H23*h1')  V2(ij0, 2)= 1; end;  %%"2^3"
  H32= ij; H32(2)= ij2(2);  if M(ij0)==M(1+H32*h1')  V2(ij0, 3)= 1; end;  %%"3^2"
 ...
  H223= ij; H223(1)= ij1(1);  H223(2)= ij1(2);  if M(ij0)==M(1+H223*h1')  V2325(ij0, 1)= 1; end; %%"2*3"
  H225= ij; H225(1)= ij1(1);  H225(3)= ij1(3);  if M(ij0)==M(1+H225*h1')  V2325(ij0, 2)= 1; end; %%"2*5"

      end;
    end;
  end;
end;


%% Проверка проверок
[sum(V2357); sum(V2); sum(V2325)]
% z=find(V2357(:,4)~=0); size(z), D4(z(1:3), :), M(z(1:3)),

Мне кажется, что для любой размерности (К) задачи совершенно безопасно выбирать коэф-ты ki из числа тех, что НОД(K, ki)=1, тогда остатки пробегают весь диапазон, и ki==1 годятся для всех K>6(меньше не смотрел).

У кого есть опровергающий пример?
...
Рейтинг: 0 / 0
13.02.2020, 15:45
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39930767
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Сделал с постоянным кол-вом циклов ("почти универсально") для K=(7:11), можно и 12 и больше, но полноценная проверка всё равно отсутствует. Комбинации вычетов создаёт универсально. Но проверки делает универсально только для х*p, где р - простой делитель размерности задачи К. Проверки типа х*p1*р2... - по-прежнему как в старом варианте - больше неохота с этим возиться.

снова целиком:
 
Код: javascript
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.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
  %%%%%%%% v3.2, for K=(7:11),  запускать  clear all; close all; row= 1; K=11; my10_mod;
pk=4; pk= length(primes(K)); T=K^pk;

%% М-ца для к-тов формулы, разные варианты: с ошибками и без
KI= zeros(100, pk);
KI(1, :)= 1;  %% double
KI(2, 1:4)= [1, 4, 6, 9]; % error "+1" for K=11 only!
KI(3, 1:4)= [0, 4, 6, 9];  %% error "+1" 
KI(4, 1:4)= [1, 0, 6, 9];  %% error "+1"
KI(5, 1:4)= [1, 4, 0, 9];  %% error "+1"
KI(6, 1:4)= [1, 4, 6, 0];  %% error "+1"
KI(7, 1:4)= [1, 1, 1, 0];  %% error "+1"
KI(8, 1:4)= [0, 1, 0, 1];  %% error "+1+1"
KI(9, 1:4)= [3 9 3 9];
KI(10, 1:4)= [1 2 3 1];
KI(11, 1:4)= [2 2 3 1];
KI(12, :)= 2;  %% no error
KI(13, :)= 5;
KI(14, :)= 3;

ki= KI(row, :)';  %% работать с этим вариантом к-тов для формулы
    
%% Вычислить массив по форуле
... h1= [1000, 100, 10, 1]; h2= 2*h1; h3= 3*h1; 
h1= zeros(1,pk); h1(pk)=1; for t= pk:-1:2  h1(t-1)= floor(K*h1(t));  end;
D4= zeros(T, pk); ... %% матрица(T*pk) всех комбинаций вычетов

%% Вычислить каждую цифру каждого числа и поместить в матрицу D4()
i1234(1:pk)= 0;
for cnt= 1:T
  %%cnt= 1+ [0 1 1 1 0]*h1'; % для проверки
  x= cnt-1;
  for t= (1:pk)  i1234(t)= floor(x/h1(t)); x= x - h1(t)*i1234(t);  end;

   %% ij= [i1234(1), i1234(2), i1234(3), i1234(4)]; ij0= ij*h1'; 
  ij(1:pk)= i1234; ij0= ij*h1'; 
  D4(1+ij0, :)= ij;
end;

    '-- ESC --',
    pause;    

M(1:T)= mod( D4*ki, K); ... %% формула классификации


%% Проверить каждую комбинацию вычетов (а лучше бы лишь некоторые)
... h1= [1000, 100, 10, 1]; h2= 2*h1; h3= 3*h1; 
h1= zeros(1,pk); h1(pk)=1; for t= pk:-1:2  h1(t-1)= floor(K*h1(t));  end;
h2= 2*h1; h3= 3*h1; h4= 4*h1; ...

  %{
   M(1+0+h1(1)+h1(3))= M(1+0);  % имитация ошибочной формулы (нек-х повторов)
   M(1+8070+h1(1)+h1(3))= M(1+8070); 
   M(1+6060+h1(1)+h1(3))= M(1+6060); 
  %}

V2357= zeros(T,pk);  V2= zeros(T, pk);  V2325= zeros(T, pk);
for cnt= 1:T
    %% BODY of Loop 
      ij(1:pk)= D4(cnt, :);  ij0= 1+ij*h1';
      ij1= mod(1+ij, K); ij2= mod(2+ij, K); ij3= mod(3+ij, K); 
      J= logical([1 1]); ij23= zeros(1,pk); ij23(J)= mod(1+ij(J), K);
      J= logical([1 0 1]); ij25= zeros(1,pk); ij25(J)= mod(1+ij(J), K);

  %% I= (M(ij)==M(ij+"1000"));
  H1= zeros(pk,pk); for t= 1:pk  H1(t,1:pk)= ij;  end;  x= diag(ones(pk,1)); H1(logical(x))= ij1';  
  Y= M(1+H1*h1'); 
  I= (M(ij0)==Y)';  V2357( 1+ ij*h1', I)= 1;

  H22= ij; H22(1)= ij2(1);  if M(ij0)==M(1+H22*h1')  V2(ij0, 1)= 1; end;  %%"2^2"
  H23= ij; H23(1)= ij3(1);  if M(ij0)==M(1+H23*h1')  V2(ij0, 2)= 1; end;  %%"2^3"
  H32= ij; H32(2)= ij2(2);  if M(ij0)==M(1+H32*h1')  V2(ij0, 3)= 1; end;  %%"3^2"
 
  H223= ij; H223(1)= ij1(1);  H223(2)= ij1(2);  if M(ij0)==M(1+H223*h1')  V2325(ij0, 1)= 1; end; %%"2*3"
  H225= ij; H225(1)= ij1(1);  H225(3)= ij1(3);  if M(ij0)==M(1+H225*h1')  V2325(ij0, 2)= 1; end; %%"2*5"

end; %for


%% Проверка проверок
[sum(V2357); sum(V2); sum(V2325)]
% z=find(V2357(:,4)~=0); size(z), D4(z(1:3), :), M(z(1:3)),
%% V23 и V25  аналогично

На этом покончил.
...
Рейтинг: 0 / 0
25.02.2020, 20:47
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932330
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Хорошую задачку сегодня задали:

Есть 100-этажный дом и 2 яйца. Нужно найти этаж, начиная с которого яйцо при падении разбивается.
Какое минимальное количество итераций для этого потребуется?

Я ее решил в том смысле, что понял принцип и нашел правильный ответ.
Но в общем виде формулу не выводил, можно это рассматривать как бонус :)
...
Рейтинг: 0 / 0
28.02.2020, 18:15
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932348
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
это классика )

 
в общем виде вопрос лучше ставить наоборот: сколько максимум этажей можем проверить на разбиваемость, если есть K яиц и лимит на N бросков.

S(k, n) = S(k-1, n-1) + 1 + S(k, n-1)

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

ну и по индукции легко доказать явную формулу (если нигде не напутал)



используя тождество C(a, b) = C(a-1, b) + C(a-1, b-1)
...
Рейтинг: 0 / 0
28.02.2020, 18:32
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932391
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Соколинский Борис,

Нужно найти минимум функции f = 100/n + n - 1, где n может принимать значения от 1 до 50.
...
Рейтинг: 0 / 0
28.02.2020, 20:03
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932393
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
iOracleDev,

поправка, плюс остаток от целочисленного деления 100%n
...
Рейтинг: 0 / 0
28.02.2020, 20:07
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932396
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Брутфорс - идём с 1 этажа вверх и кидаем. Как только разобъется - нашли.

Оптимизация этого брутфорса - найти удачное начальное приближение. Желательно с запасом в 1-2 этажа.
Первый бросок - пристрелочный. Второй - доказательство правоты.

Для улучшения КМК можно вспомнить физику Ньютона. Как там с падением. И как разбивание яйца зависит от
высоты. В практике оно должно разбиться уже на 1 этаже но мы берем яйцо математическое. Тоесть возможно
оно гораздо твёрже. У ньютона кажется при одинаковом ускорении свободного падения скорость растет
квадратично. Тоесть формула должна иметь вид квадратного корня.
...
Рейтинг: 0 / 0
28.02.2020, 20:14
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932397
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Нужно найти минимум функции f = 100/n + 100%n + n - 1 2
n от 1 до 50, % - ремайндер оператор.

PS: ответ соответственно n = 10, а итераций 18
...
Рейтинг: 0 / 0
28.02.2020, 20:16
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932401
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
iOracleDev,

Можно меньше
...
Рейтинг: 0 / 0
28.02.2020, 20:29
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932420
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Соколинский Борис,
этажи для первого яйца:
1, 12, 25, 37, 48, 58, 67, 75, 82, 88, 93, 97, 100
(от 100 назад через 3 на первом шаге, + 1 на каждом следующем.)

если на первом этаже яйцо точно не бьется, то 13 для всех кроме случая попадания на 100, тогда 14
...
Рейтинг: 0 / 0
28.02.2020, 21:53
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932423
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
booby,
если разобьется на 25, то 15.
Идея присутствует, но нуждается в рихтовке.
...
Рейтинг: 0 / 0
28.02.2020, 22:07
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932424
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
авторесли на первом этаже яйцо точно не бьется
формулировка кривая, но лучше не сумел сказать.
если бы было известно, что на первом шаге точно не бьется, его можно было бы и не бросать.
...
Рейтинг: 0 / 0
28.02.2020, 22:11
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932425
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Соколинский Борис,

мне лень рихтовать, - это неравномерный поиск.

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

Интереснее было бы почувствовать, где и как такие последовательности появляются в реальных задачах.
я пока не могу сообразить хорошего применительного случая.

-----------
когда шел с обратной стороны, получалось 1, 14, 25...
но что что-то не срослось и побежал назад от ста. от ста.
может оно и с обеих сторон не сходится - тогда я не знаю как правильно сращивать поход слева с походом справа.
...
Рейтинг: 0 / 0
28.02.2020, 22:17
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932432
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
booby,

собственно да, в обе стороны на "пару" не сходится.
предпоследний шаг надо "рихтовать".
я пока не понимаю, как это назвать и что это значит...
...
Рейтинг: 0 / 0
28.02.2020, 22:31
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932435
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
booby,

1, 14, 26, 37... и далее по предыдущему списку
...
Рейтинг: 0 / 0
28.02.2020, 22:42
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932437
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Соколинский Борис
iOracleDev,

Можно меньше

В принципе идея понятна, сохранять постоянное количество итреаций и найти минимум стартового интервала.

15
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
length = 85   100-length = 15     interval = 15   count = 1   interval-1+count = 15
length = 71   100-length = 29     interval = 14   count = 2   interval-1+count = 15
length = 58   100-length = 42     interval = 13   count = 3   interval-1+count = 15
length = 46   100-length = 54     interval = 12   count = 4   interval-1+count = 15
length = 35   100-length = 65     interval = 11   count = 5   interval-1+count = 15
length = 25   100-length = 75     interval = 10   count = 6   interval-1+count = 15
length = 16   100-length = 84     interval = 9   count = 7   interval-1+count = 15
length = 8   100-length = 92     interval = 8   count = 8   interval-1+count = 15
length = 1   100-length = 99     interval = 7   count = 9   interval-1+count = 15

14
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
length = 86   100-length = 14     interval = 14   count = 1   interval-1+count = 14
length = 73   100-length = 27     interval = 13   count = 2   interval-1+count = 14
length = 61   100-length = 39     interval = 12   count = 3   interval-1+count = 14
length = 50   100-length = 50     interval = 11   count = 4   interval-1+count = 14
length = 40   100-length = 60     interval = 10   count = 5   interval-1+count = 14
length = 31   100-length = 69     interval = 9   count = 6   interval-1+count = 14
length = 23   100-length = 77     interval = 8   count = 7   interval-1+count = 14
length = 16   100-length = 84     interval = 7   count = 8   interval-1+count = 14
length = 10   100-length = 90     interval = 6   count = 9   interval-1+count = 14
length = 5   100-length = 95     interval = 5   count = 10   interval-1+count = 14
length = 1   100-length = 99     interval = 4   count = 11   interval-1+count = 14

13
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
length = 87   100-length = 13     interval = 13   count = 1   interval-1+count = 13
length = 75   100-length = 25     interval = 12   count = 2   interval-1+count = 13
length = 64   100-length = 36     interval = 11   count = 3   interval-1+count = 13
length = 54   100-length = 46     interval = 10   count = 4   interval-1+count = 13
length = 45   100-length = 55     interval = 9   count = 5   interval-1+count = 13
length = 37   100-length = 63     interval = 8   count = 6   interval-1+count = 13
length = 30   100-length = 70     interval = 7   count = 7   interval-1+count = 13
length = 24   100-length = 76     interval = 6   count = 8   interval-1+count = 13
length = 19   100-length = 81     interval = 5   count = 9   interval-1+count = 13
length = 15   100-length = 85     interval = 4   count = 10   interval-1+count = 13
length = 12   100-length = 88     interval = 3   count = 11   interval-1+count = 13
length = 10   100-length = 90     interval = 2   count = 12   interval-1+count = 13
length = 9   100-length = 91     interval = 1   count = 13   interval-1+count = 13
length = 8   100-length = 92     interval = 1   count = 14   interval-1+count = 14
length = 7   100-length = 93     interval = 1   count = 15   interval-1+count = 15
length = 6   100-length = 94     interval = 1   count = 16   interval-1+count = 16
length = 5   100-length = 95     interval = 1   count = 17   interval-1+count = 17
length = 4   100-length = 96     interval = 1   count = 18   interval-1+count = 18
length = 3   100-length = 97     interval = 1   count = 19   interval-1+count = 19
length = 2   100-length = 98     interval = 1   count = 20   interval-1+count = 20
length = 1   100-length = 99     interval = 1   count = 21   interval-1+count = 21


Как выразить простой формулой не знаю.
...
Рейтинг: 0 / 0
28.02.2020, 22:59
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932454
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
докрутилось и сложилось в пазл:

сумма 1+2+3+4+5+6+7+8+9+10+11+12+13+14=105

Поэтому уменьшаем пять правых слагаемых на единицу каждый:

1+2+3+4+5+6+7+8+9+9+10+11+12+13=100
так получаем число элементов в слоте

завершение раскладки должно быть таким:
слот старт до штук в слоте13100- 1129899211959731091944986905880856773797665728556649447559337461022636111142512011313

Первый бросок делаем в слот 1 по его левому краю - 14
если шар разбился, идем в предыдущий слот со вторым шаром и шагаем по не посещенным этажам,
если нет, продолжаем в следующем слоте с первым шаром, и бросаем с левого крайнего (нижнего) этажа слота.

последовательность бросков первого шара 14,26,37,47,56,65,73,80,86,91,95,98,100

PS
что там рассказывают про "динамическое программирование"?

PS2 что-то лихо в правых (верхних) двойках запутался...
(;;
...
Рейтинг: 0 / 0
29.02.2020, 04:11
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932472
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
booby

последовательность бросков первого шара 14,26,37,47,56,65,73,80,86,91,95,98,100
Все верно.

В случае яиц шаров алгоритм понятен, а вот с тремя уже не очень.
Объяснения под спойлером не понял.
...
Рейтинг: 0 / 0
29.02.2020, 10:11
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932532
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Я сделал то же самое но с другого конца, проверяя гипотезу, что например 15 это минимальное число итераций, первый шаг проверка на 15 этаже, если первое золотое яичко разбилось, то проверяем с первого по 14, соответственно худший случай это 15 итераций, далее чтобы не ухудшить количество итераций (одну мы уже сделали), следующий шаг 14 (29 этаж) это вторая итерация, если яйцо разбилось, то нужно проверить 13 этажей, получаем 13 + 2 итераций (2 - предыдущие уже сделанные итерации) и так далее, получается каждый следующий шаг для условия непревышения заданного количества итераций уменьшается на единицу.

У вас сколько минимум получился?
...
Рейтинг: 0 / 0
29.02.2020, 16:08
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932541
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Объяснения под спойлером не понял.
речь об этом? 22089442

Попробую "разжевать")

Итак, у нас в запасе K яиц, ограничение на N бросков.
Какова максимальная высота дома, чтобы мы с такими ограничениями могли выяснить, с какого этажа разбивается яйцо. Ну или вообще не разбивается.

Искомую функцию максимальной высоты обозначим как S(K, N)

1) Более простой кейс - яиц бесконечно много (или хотя бы не меньше чем N), в общем, их экономить не надо и мы ориентируемся только на броски.
Очевидно, наилучшая стратегия - поиск делением пополам.
Бросаем со среднего этажа, если разбилось, надо проверять нижнюю часть, с лимитом N-1, иначе верхнюю часть, тоже с лимитом N-1, потому что один бросок уже сделан.
Тогда получается
S(N) = S(N-1) + 1 + S(N-1)
S(0) = 0
что дает S(N) = 2 N - 1

2) Если вернуть в игру К, то поиск немного "перекособачивается".
Если на первом броске яйцо разбилось, то для проверки нижней части будет K-1 яиц и N-1 бросков. Если не разбилось, то для верхней части имеем K яиц и N-1 бросков.
Формула будет аналогичная:

S(K, N) = S(K-1, N-1) + 1 + S(K, N-1)
S(0, N) = S(K, 0) = 0

В принципе, можно считать по этой формуле, можно переделать в явный вид, но для общего случая там сумма биномиальных коэффициентов, в для конкретных K - полином от N
например, если 2 яйца, то S(2, N) = (N 2 + N) / 2
для 3 яиц S(3, N) = (N 3 + 5*N) / 6

и т.е.

Например, 100 этажей.
если 2 яйца, то за 13 бросков можем проверить максимум 91 этаж, за 14 будет 105 этажей, то есть 14 достаточно
если 3 яйца, то 8 бросков проверяют 92 этажа, 9 бросков хватит на 129, то есть надо 9 бросков.
...
Рейтинг: 0 / 0
29.02.2020, 16:39
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932644
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
Соколинский Борис
Объяснения под спойлером не понял.
речь об этом? 22089442
Попробую "разжевать")
Получилось, спасибо :)
А как для произвольных (K, N) должен выглядеть алгоритм обхода?
...
Рейтинг: 0 / 0
01.03.2020, 12:35
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39932704
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
авторА как для произвольных (K, N) должен выглядеть алгоритм обхода?

вероятно таким:

1) строишь возвратную последовательность для K
2) выравниваешь её на фактическое N
3) кладешь M = N - это число не обследованных шаров
4) шагаешь по полученной возвратной последовательности обратным ходом,
сохраняя номер броска в переменной i, на каждом шаге уменьшая M: M=M-1
5) отыскиваешь i, на котором разбился первый шар
6) Если M=0 To Стоп
7) присваиваешь - K=K-i, N = (Число_элементов в слоте_предшествующем_i - 1), M = N
8) GOTO 1


Но интереснее было бы увидеть пример практической ценности.
Генераторы случайных чисел?
- не похоже, - здесь явно пирамидально закошеный поиск.
Хде, хде его применимость, какие ленты с барабанами по нему плачут?
...
Рейтинг: 0 / 0
01.03.2020, 15:24
| Ответить | Цитировать | Написать  
25 сообщений из 339, страница 7 из 14
  7  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39932396&tid=1339678]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 163ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 66ms
get tp. blocked users:
 2ms
others: 241ms
total:  519ms
созд. / загр.: 519ms
x
x
Закрыть


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