CD
я бы поверил, если бы мне сказали, что там n!/e^n :)
Size: a a a
2021 April 02
2021 April 03
NK
Strong conjecture: there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n; weak conjecture: lim_{n -> infinity} (1/n) * log(n!/a(n)) = constant = 0.90.... - Benoit Cloitre, Nov 10 2002
NK
В принципе то что решений так много объясняет почему случайные локальные оптимизации так хорошо работают для поиска хоть какого-то решения
NK
вот тут достаточно большой обзор на эту тему
NK
NE
вызывая
rand7 я генерирую a = log2(7) бит. Мне надо b = log2(10). Можно ли придумать какой-то "аккумулятор" acc, который бы комбинировал эти a бит с очередной порцией a бит, пока сумма не превысит b бит, а затем можно было бы извлечь b бит и floating-point "счётчик количества бит в аккумуляторе" уменьшить на b? Т.е. вообще без rejection обойтись?Проще сделать то что ты спрашиваешь так:
Сгенерировать 10-разрядное число по основанию 7
Перевести в десятичное число и разделить по разрядам - теперь мы имеем 7 случайных числе от 0 до 10,
Сгенерировать 10-разрядное число по основанию 7
Перевести в десятичное число и разделить по разрядам - теперь мы имеем 7 случайных числе от 0 до 10,
NE
хотя вот сейчас подумал, что глупость сделал, оно так не работает
AT
Nyc Enas
Проще сделать то что ты спрашиваешь так:
Сгенерировать 10-разрядное число по основанию 7
Перевести в десятичное число и разделить по разрядам - теперь мы имеем 7 случайных числе от 0 до 10,
Сгенерировать 10-разрядное число по основанию 7
Перевести в десятичное число и разделить по разрядам - теперь мы имеем 7 случайных числе от 0 до 10,
да уже довели до ума идею: вот
чтобы как можно меньше вызовов rand7 было, нужно вместо
чтобы как можно меньше вызовов rand7 было, нужно вместо
while (h < 10) сделать while (h < std::numeric_limits<int>::max() / 7)
CD
да уже довели до ума идею: вот
чтобы как можно меньше вызовов rand7 было, нужно вместо
чтобы как можно меньше вызовов rand7 было, нужно вместо
while (h < 10) сделать while (h < std::numeric_limits<int>::max() / 7)а зачем тут лимиты?
class Solution {
public:
int rand10() {
int acc = 0;
int acc_max = 0;
for (;;) {
acc = acc * 7 + rand7() - 1;
acc_max = acc_max * 7 + 7 - 1;
if (acc_max >= 10) {
acc_max %= 10;
if (acc > acc_max) {
return (acc - acc_max) % 10 + 1;
}
}
}
}
};CD
или надо в потоке и арифметикой пересчитывать?
AT
или надо в потоке и арифметикой пересчитывать?
В потоке, да. На 1 вызов rand10 как можно меньше вызовов rand7. Чтобы rejection как можно реже срабатывал, лучше сделать так, как у меня. В пределе получается примерно 1.183 вызовов rand7 на один rand10. Вывести этот предел аналитически я затрудняюсь.
CD
В потоке, да. На 1 вызов rand10 как можно меньше вызовов rand7. Чтобы rejection как можно реже срабатывал, лучше сделать так, как у меня. В пределе получается примерно 1.183 вызовов rand7 на один rand10. Вывести этот предел аналитически я затрудняюсь.
class Solution {
public:
int acc = 0;
int acc_max = 0;
void push_randk(int x, int k) {
acc_max = acc_max * k + (k - 1);
acc = acc * k + x;
}
int pull_randk(int k) {
if (acc_max < k)
return -1;
int extra_max = acc_max / k;
acc_max = acc_max % k;
if (acc <= acc_max)
return -1;
int extra_acc = (acc - acc_max - 1) / k;
int result = (acc - acc_max - 1) % k;
acc = 0;
acc_max = 0;
push_randk(extra_acc, extra_max);
return result;
}
int rand10() {
for (;;) {
if (auto x = pull_randk(10); x != -1)
return x + 1;
push_randk(rand7() - 1, 7);
}
}
};я немного поблуждал в трёх соснах, такое получилось
CD
на литкоде можно cerr как-то получить?
CD
лень локально гонять
AT
на литкоде можно cerr как-то получить?
Да. На премиуме. В debug
AT
И cout
AT
class Solution {
public:
int acc = 0;
int acc_max = 0;
void push_randk(int x, int k) {
acc_max = acc_max * k + (k - 1);
acc = acc * k + x;
}
int pull_randk(int k) {
if (acc_max < k)
return -1;
int extra_max = acc_max / k;
acc_max = acc_max % k;
if (acc <= acc_max)
return -1;
int extra_acc = (acc - acc_max - 1) / k;
int result = (acc - acc_max - 1) % k;
acc = 0;
acc_max = 0;
push_randk(extra_acc, extra_max);
return result;
}
int rand10() {
for (;;) {
if (auto x = pull_randk(10); x != -1)
return x + 1;
push_randk(rand7() - 1, 7);
}
}
};я немного поблуждал в трёх соснах, такое получилось
randX in {1, 2, ..., X}AT
Учтено?
CD
randX in {1, 2, ..., X}ну 1 я вычитаю/прибавляю везде подряд