Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Серый форум → Общение → Script-Coding.com community → OFF: Прошу подключиться к решению загадки… — II
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Можно вывести формулу, однозначно описывающую эту зависимость.
Ага, точно:
KillSecond(n)
{
Loop
{
pow := 2**A_Index ; A_Index — итератор, начинается с 1
if (pow = n)
Return 1
else if (pow > n)
Return 2*n + 1 - pow
}
}
teadrinker
Без цикла! 
kill each second
input: n
p = ceil log2 n
result = n * 2 + 1 - 2**p
if ( result > n ) {
result = 1
}
return result
Тогда через двоичный логарифм, но в AHK его нет
Если мне не изменяет память log2 нет ни в одном ЯП. А Ассемблер (интеловский) умеет вычислять любые логарифмы.
Двоичный можно так получить:
log2(x) = lg(x) * log2(10) = lg(x) * 3.3219280948873626Либо так, чтобы константу не запоминать:
log2(x) = lg(x) / lg(2)
Вот так для 32-битного n:
MsgBox, % KillSecond(31)
KillSecond(n)
{
pow := MinPow(n)
if (pow = n)
Return 1
else if (pow < n)
Return 2*n + 1 - pow*2
}
MinPow(x) ; наибольшее снизу значение степени двойки
{
x |= (x >> 1)
x |= (x >> 2)
x |= (x >> 4)
x |= (x >> 8)
x |= (x >> 16)
return x & ~(x >> 1)
}
Такое чувство, что у задачи нет точного решения. Называй любое - фиг докажешь, что оно неправильное.
О, можно короче:
MsgBox, % KillSecond(7)
KillSecond(n)
{
pow := MinPow(n)
Return 2*n + 1 - pow*2
}
MinPow(x) ; наибольшее снизу значение степени двойки
{
Loop 5
x |= (x >> 2**(A_Index - 1))
return x & ~(x >> 1)
}
Такое чувство, что у задачи нет точного решения. Называй любое - фиг докажешь, что оно неправильное.
К счастью доказывать надо правильность решения, а не наоборот . С доказательством и обобщениями можно ознакомится в этой книге, параграф 1.3.
или циклический сдвиг влево на один бит. Для получения результата на привычной x86-64 нужно обнулить старший бит, результат сдвинуть влево на 1 бит и установить младший бит. Про старший бит см. эту статью и обсуждение. И прямая ссылка на оригинальную книгу.
формулы оформлены неправильно. В левой части 1 и 4 измеряются в минутах, а в правой части 1 измеряется в штуках. Чтобы не путаться, в правой части лучше написать 1x или просто x.
Это нормальная практика - либо единицы измерения не указываются(как у меня), либо указываются, но точно не вперемешку как ты предлагаешь.
Для получения результата на привычной x86-64 нужно обнулить старший бит, результат сдвинуть влево на 1 бит и установить младший бит
Осталось только это все вычислить в уме, пока тебя пытаются пристрелить 
Осталось только это все вычислить в уме, пока тебя пытаются пристрелить
Без проблем, поскольку население земли меньше (2^33)-1 человек . Нужно только помнить степени двойки и вычитать 9-значные числа в уме, не так уж это и сложно.
upd. Rumata, нельзя, на степенях двойки не будет работать.
на степенях двойки не будет работать.
таки да.
Не знаю, правда, насколько это оптимально(JScript):
n=1548; //Исходное количество игроков
k=n;
i=-1;
while (k>0)
{
k=Math.floor(k/2);
i++;
}
R = 2*(n-Math.pow(2,i))+1;
WScript.Echo('Result = '+R);
Мне видится излишним эмулировать вычисление log2:
i = Math.floor(Math.log(n) / Math.LN2);
R = 2 * n - Math.pow(2, i + 1) + 1;
Мне видится излишним эмулировать вычисление log2:
Да, пожалуй, хотя особой погоды не делает.
n=5; //Исходное количество игроков
WScript.Echo('Result = '+String(2*(n-Math.pow(2,Math.floor(Math.log(n)/Math.LN2)))+1));
Давайте чутка отдохнём от скриптов . Игра на угадывание чисел:
Играют двое. Первый загадывает число от 1 до 610. Второй должен угадать это число задавая вопросы вида "есть ли среди чисел {1, 2, 5, ...} загаданное?". За каждый вопрос второй участник платит 1$ и ещё 1$ если ответ первого игрока был отрицательным. Какая минимальная сумма денег нужна второму игроку, чтобы точно угадать загаданное число?
загаданное число меньше 300? - Да ( +1$ )
загаданное число больше 10? - Нет ( +2$ )
это число 8? - Да ( +1$ )
Ответ 8. Второму игроку потребовалось 4$.
Давайте чутка отдохнём от скриптов
. Игра на угадывание чисел:
Играют двое. Первый загадывает число от 1 до 610. Второй должен угадать это число задавая вопросы вида "есть ли среди чисел {1, 2, 5, ...} загаданное?".
Попробовать последовательно разбивать отрезок 1 - 610 целочисленно пополам, т.е:
Загаданное число меньше 305 - Да;
Загаданное число меньше 152 - Нет (значит число лежит в отрезке 152 - 305);
Загаданное число больше 152+152/2 = 228 - Нет (значит число лежит в отрезке 152 - 228);
и.т.д
В итоге, общее количество попыток, в данном случае (точно не уверен), сводится к логарифму floor(Log2(610)) + 1(для окончательного указания числа) = 10.
Скрипт-угадайка(JScript). Требуется отгадать число из отрезка 1-10:
//---------------------------------------------
// Угадайка. Требуется отгадать число из отрезка 1-10.
//---------------------------------------------
var ws = new ActiveXObject('WScript.Shell');
iYes = 6;
iCancel = 2;
var b, k ,i;
//var u = Math.round(Math.random()*10); // Загаданное число
var u = 5; // Загаданное число
var m = 10; // Максимальное значение
var n0 = 0;
var n1 = m;
//---------------------------------------------
i = 1;
while (1)
{
if (((u<n0+1)&&(u<n1))||((u>n0+1)&&(u>n1))){ws.PopUp('Вы проиграли.', -1, 'Угадайка', 64); break;}
if (n0+1==n1){ws.PopUp('Указанное число: ' + u, -1, 'Угадайка', 64); break;}
b = (n1-n0)/2
k = Math.floor(n0 + b);
iAnsw = ws.PopUp('Попытка ' + i+'. Указанное число лежит в отрезке ' + String(n0+1) + '_' + String(n1) + '. Указанное число больше ' + k + '?', -1,'Уточнение отрезка',3 + 32)
if (iAnsw == iCancel)
{
break;
}
else if(iAnsw == iYes)
{
n0 = k
}
else
{
n1 = k
}
i++;
}
//---------------------------------------------
Александр_ пишет:Давайте чутка отдохнём от скриптов
Играют двое. Первый загадывает число от 1 до 610. Второй должен угадать это число задавая вопросы вида "есть ли среди чисел {1, 2, 5, ...} загаданное?".Попробовать последовательно разбивать отрезок 1 - 610 целочисленно пополам, т.е:
В моей цитате нет вопроса . вопрос был ниже по тексту:
За каждый вопрос второй участник платит 1$ и ещё 1$ если ответ первого игрока был отрицательным. Какая минимальная сумма денег нужна второму игроку, чтобы точно угадать загаданное число?
Ну и скрипт, тогда уж должен отгадывать, а не загадывать 
. Потом можно будет разные скрипты друг с другом стравливать - загадать число, кто первый угадает, тот и победил .
Почему именно 610? Не 500, 600, 1000 или 618.
Играют двое. Первый загадывает число от 1 до 610. Второй должен угадать это число задавая вопросы [...] За каждый вопрос второй участник платит 1$ и ещё 1$ если ответ первого игрока был отрицательным. Какая минимальная сумма денег нужна второму игроку, чтобы точно угадать загаданное число?
Математическое обоснование слабое, но какое есть.
Для угадывания числа из ряда 1, 2, ... N требуется не более log2 N итераций. За каждый отрицательный ответ мы платим вдвойне. То есть мы можем отгадать число, заплатив за это сумму
не менее floor log2 N и
не более 2 * ceil log2 N
Для N = 610
floor log2 N = 9
Почему именно 610? Не 500, 600, 1000 или 618.
Это подсказка .
Математическое обоснование слабое, но какое есть.
Всё-таки не менее , но нужно всё равно рассматривать худший сценарий, т.е. потребуется 20$. Но можно дешевле.
Всё-таки
Все время задавая вопрос "Загаданное число больше чем M?", 610 отгадывается за 9$. 1 - за 19$.
Какая минимальная сумма денег нужна второму игроку, чтобы точно угадать загаданное число?
Ответ на вопрос - 9 (floor log2 610), не 10 (ceil log2 610).
Все время задавая вопрос "Загаданное число больше чем M?", 610 отгадывается за 9$. 1 - за 19$.
Либо 18 и 10, либо 20 и 9, смотря как округлять нечётные. 19 тут вообще никак не получить, оно же чётное, а если ответ всё время "нет", то сумма будет нечётной.
Какая минимальная сумма денег нужна второму игроку, чтобы точно угадать загаданное число?
Ответ на вопрос - 9 (floor log2 610), не 10 (ceil log2 610).
Разумеется нет, этих сумм не хватит ни при какой стратегии. При такой стратегии ответом будет в лучшем случае 18(), опять же - там две различные стратегии "половинного деления", но обе не оптимальны.
19 тут вообще никак не получить
Эксперимент утверждает обратное.
Эксперимент утверждает обратное.
Продемонстрируй.
1 из (1, 2, 3)
больше 2? - нет (2$)
равно 1? - да (1$)
1 из (1, 2, 3)
больше 2? - нет (2$)
равно 1? - да (1$)
это противоречит фразе "Все время задавая вопрос "Загаданное число больше чем M?"". И худшим тут становится число 2.
С округлением в большую сторону так получается:
>305 - 2
>163 - 4
> 77 - 6
> 39 - 8
> 20 - 10
> 10 - 12
> 5 - 14
> 3 - 16
> 2 - 18
> 1 - 20
ответ - 1, цена 20$Rumata пишет:Почему именно 610? Не 500, 600, 1000 или 618.
Это подсказка
Смутное предположение: может быть нужно делить на e? т.е минимальное количество попыток:
n = Math.floor(Math.pow(610,1/Math.E))
Poltergeyst, нужно найти не попытки, а именно деньги. И основание натурального логарифма тут не при чём . Решайте упрощённую задачу - начните с n=1 и постепенно увеличивайте. Я именно так и решал и заняло это совсем не много времени .
Ладно, вот решение двумя способами, без подробностей, только основные идеи:
Выписываем в столбик решения для малых значений:
f(1) = 0
f(2) = 2
f(3) = 3
f(4) = 4
f(5) = 4
f(6) = 5
f(7) = 5
f(8) = 5
f(9) = 6
f(10) = 6
f(11) = 6
f(12) = 6
f(13) = 6
f(14) = 7
и видим, что значение функции меняется только после достижения чисел Фибоначчи. Т.е. нужно на каждом шаге выбирать любое подмножество, мощность(к-во элементов) которого равна максимальному возможному числу Фибоначчи(предполагается, что нельзя назвать всё множество, в этом просто нет смысла). Ну а нужная сумма равна номеру ближайшего числа Фибоначчи с каким-то сдвигом, я не смотрел с каким именно.
Если подойти к решению с другой стороны и пытаться не угадать всё решение сразу, а придумать в какой пропорции делить множество на каждом шагу, то получается такая цепь рассуждений(расчёты не точные, просто начальное приближение):
Если делить множество пополам, то в лучшем случае(угадывать и платить только 1$) нам потребуется долларов, а в худшем вдвое больше -
долларов.
Если же делить множество в пропорции 2:1, то в лучшем случае(если всё время будем ошибаться) нам потребуется долларов, а в худшем
.
Поскольку нужно максимально улучшить худший случай, то нужно потребовать его равенства с лучшим:
Решаем, выбираем подходящий корень - . Т.е. на каждом ходу нужно делить множество в пропорции золотого сечения. Формулу для точной суммы отсюда получить сложно, она будет выглядеть так:
Раз все молчат продолжу вспоминать задачки. Опять игра и опять "угадайка". Два игрока, первый загадывает число от 1 до 3 включительно, а второй пытается угадать. Если второй игрок на первом ходу ошибается, то первый даёт ему подсказку "больше" или "меньше". Если второй игрок угадывает с первого раза, то первый выплачивает ему 1$, если со второго, никто ничего не платит, если с третьего, то второй платит первому 1$. Как должен действовать второй игрок, чтобы максимизировать свой выигрыш независимо от действий первого игрока? Сколько он выиграет за 100 партий при грамотной игре оппонента(в среднем)?
Мда, похоже я тут сам себя развлекаю .
В теории игр такие игры называются матричными, есть даже онлайн сервисы для решения таких игр, например этот.
В данном конкретном случае первый игрок имеет 3 чистых стратегии- загадать единицу, загадать двойку и загадать тройку. Второй игрок пять - отгадывать числа в следующем 1-2, 1-3, 2-x, 3-1 и 3-2. Получается матрица 5х3, решив игру найдём цену игры 0.2$, т.е. в среднем второй игрок будет выигрывать по 20$ за 100 партий. При этом играть он должен в 60% случаев по стратегии 2-x, в 20% по стратегии 1-3 и с той же частотой 3-1, остальные ненужно использовать никогда.
Два игрока, первый загадывает число от 1 до 3 включительно, а второй пытается угадать. Если второй игрок на первом ходу ошибается, то первый даёт ему подсказку "больше" или "меньше". Если второй игрок угадывает с первого раза, то первый выплачивает ему 1$, если со второго, никто ничего не платит, если с третьего, то второй платит первому 1$. Как должен действовать второй игрок, чтобы максимизировать свой выигрыш независимо от действий первого игрока? Сколько он выиграет за 100 партий при грамотной игре оппонента(в среднем)?
Видел твою задачу, но по каким-то причинам отвечать не стал. Воспроизвожу свой ответ.
При ограниченном наборе ответов - только "больше" или "меньше", на мой взгляд, лучшей стратегией будет ответ 2. из 100 партий угадывающий отгадает 33 раза (в среднем).
лучшей стратегией будет ответ 2
Я бы на месте первого игрока сразу перестал загадывать 2.
Rumata пишет:лучшей стратегией будет ответ 2
Я бы на месте первого игрока сразу перестал загадывать 2.
Чистая вторая стратегия является наиболее "естественной" из-за т.н. "неприятия риска". Следуя ей ты точно не проиграешь, но и выигрыша она не гарантирует. На самом деле если второй игрок будет следовать своей оптимальной стратегии, то ты тоже выиграешь 20$ за 100 партий, поскольку оптимальным является соотношение 40/20/40 (загадать единицу/двойку/тройку).
Но если оппонентом будет teadrinker, то он вычислит эту стратегию и не будет загадывать двойку вообще, устремив выигрыш к нулю .
Задача для языка 1С .
Есть таблица с колонками "Дата", "Товар" и "Сумма".
Таким образом, в каждой дате содержится товаров на некоторую сумму.
Известно, что эта сумма в каждой дате не превышает некоторое число МаксСумма.
Нужно оптимизировать таблицу таким образом, чтобы:
1) в ней стало как можно меньше уникальных дат;
2) условие непревышения числа МаксСумма в каждой дате продолжало выполняться.
Таким образом, нужно просто поменять некоторые даты в некоторых строках.
В языке 1С есть хорошая функция "Свернуть" у объекта таблицы, которая возвращает новую таблицу, а в качестве двух своих параметров принимает имена колонок. Строки, у которых совпадают значения в колонках, указанных в первом параметре, сворачиваются в одну строку. Значения этих строк, хранящиеся в колонках, указанных во втором параметре, накапливаются. Т.е., например, таблицу сумм по датам можно получить одной командой: свернуть по "Дата", накапливая "Сумма".
Прошу описать алгоритм словесно .
The gray Cardinal, это в какой версии платформы?
The gray Cardinal, это в какой версии платформы?
8.2.
И ещё, для не слишком знакомых с этим языком: сортировка таблицы по любому полю — это тоже одна команда. Циклы примерно как в VBScript (да и во всех языках).
8.2.
.
И ещё, для не слишком знакомых с этим языком: …
Для совсем не знакомых — без разницы .
alexii, сортировка и свёртка таблиц, а тем более циклы, есть и в 7.7, версия здесь не принципиальна.
Мне б ещё задание само понять .
P.S. «Что толку в книжке, — подумала Алиса, — если в ней нет ни картинок, ни разговоров?»
Ребёнку в школе задание дали:
Варианты?
О 1,4 [] 1,4
x := 1
Loop
{
MsgBox О %x% [] %x%
x := x+0.2
}
Желательно закономерность сформулировать.
O55555/\55555
O55555/\55555
Нет, ты не понял, последнее только в качестве примера, оно решено уже.
О 1,4 [] 1,4
x := 1 Loop { MsgBox О %x% [] %x% x := x+0.2 }
Едва ли, запятая там не является разделителем между целой и десятичной частью, это второй класс
Необязательно знать про дроби, чтобы найти закономерность. Для второклассника запятая это просто значок, как кружочек с треугольником.
Ну смотри, в задании в начале идёт 01[]101,2
А у тебя получается 1,2[]01,4
Не вижу аналогии между 101,2 и 01,4.
Да и откуда там 4, скорей уж 3.
Кружочек 1 запятая 3 квадратик 1 запятая 3.
Ребёнку в школе задание дали:
Варианты?
Решили:
Не вижу аналогии между 101,2 и 01,4.
Действительно, без дробей нелогично.
Да тут главная загвоздка была в том, что 0 — это не ноль, и к цифрам не относится, а просто кружочек.
Бедные дети, бедные родители .
Чтобы отправить ответ, вы должны войти или зарегистрироваться
