Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 179
1. Написать программу, которая печатает числа от 1 до 10000 не используя никаких сравнений.
perl -E'say for 1..1000'
Условие соблюдено, я не использовал ни одного сравнения, а какое там syntax tree перл у себя внутри построит или какие оптимизации сделает — это уже другой вопрос.
Вот почему я считаю, что правильная формулировка вопроса очень важна :)
На плюсах таких способов много, вот один из них.
std::vector<int> vec(10000);
std::iota(vec.begin(),vec.end(),1);
std::copy(vec.begin(),vec.end(),std::ostream_iterator<int>(std::cout, ", "));
или:
или в C++11
На Shell это будет вообще:
Скрытый текст
правда на больших N может потребоваться увеличить глубину рекурсии при инстанцировании.
template<int n>
void print()
{
cout << n << endl;
print<n+1>();
}
template<>
void print<10000>()
{
cout << 10000 << endl;
}
int main()
{
print<1>();
}
правда на больших N может потребоваться увеличить глубину рекурсии при инстанцировании.
или в C++11
Скрытый текст
int a[10000];
int v = 1;
for (auto i : a) cout << (v++) << endl;
На Shell это будет вообще:
Скрытый текст
seq 1 10000
Недавно видел похожий конкурс: loop without looping.
ruby -e "10000.times{|i| puts i}"
Можно просто написать на паскале))
for i := 1 to 1000 writeln(i);
Ну все же очень просто, никаких сравнений, даже в машинных кодах можно без них написать:
print(1);
print(2);
…
print(10000);
print(1);
print(2);
…
print(10000);
1. Написать программу, которая печатает числа от 1 до 10000 не используя никаких сравнений.
Тут несколько довольно очевидных решений.
Если
if(x) не считается сравнением, то тогда сработает простой нисходящий цикл.Скрытый текст
for (int i = 10;; --i)
{
if (!i)
{
break;
}
printf("%i\n", 11-i);
}Если считается, то сработает тот же цикл с switch.
Скрытый текст
for (int i = 10;; --i)
{
switch (i)
{
case 0:
return 0;
default:
printf("%i\n",11-i);
}
}Наличие реальных операций сравнения в генерируемом коде зависит от компилятора.
Чуть более «веселое» решение доступно в языках, где деление на ноль вызывает исключение.
Как-то так
Рекурсия при желании заменяется на бесконечный цикл, работающий аналогичным образом.
def print_number(x):
try:
print_number(x-x/x)
print(x)
except ZeroDivisionError:
pass
print_number(10)Рекурсия при желании заменяется на бесконечный цикл, работающий аналогичным образом.
Linq-шное коротенечкое решение для C#
Enumerable.Range(0,10001).ToList().ForEach(Console.WriteLine);
Enumerable.Range(0,10001).ToList().ForEach(Console.WriteLine);
Такой switch без сравнений не откомпилируется.
то могло бы, но ни один компилятор этого не сделает — обязательно влепит проверку, что индекс в таблице переходов лежит в диапазоне {0,1}.
Правда, здесь сравнения могут спрятаться в puts, но можно избавиться и от них.
Вот если так
for(int i=1;;i++){
switch(i/10001){
case 0:
printf("%d\n",i);
break;
case 1:
return;
}
}
то могло бы, но ни один компилятор этого не сделает — обязательно влепит проверку, что индекс в таблице переходов лежит в диапазоне {0,1}.
Совсем без сравнений можно сделать так
void Print(char c1,char c2,char c3,char c4){
putchar(' ');
putchar(c1); putchar(c2); putchar(c3);
putchar(c4); putchar('\n');
}
void F11(char c1,char c2,char c3){
Print(c1,c2,c3,'0'); Print(c1,c2,c3,'1'); Print(c1,c2,c3,'2'); Print(c1,c2,c3,'3');
Print(c1,c2,c3,'4'); Print(c1,c2,c3,'5'); Print(c1,c2,c3,'6'); Print(c1,c2,c3,'7');
Print(c1,c2,c3,'8'); Print(c1,c2,c3,'9');
}
void F12(char c1,char c2){
F11(c1,c2,'0'); F11(c1,c2,'1'); F11(c1,c2,'2'); F11(c1,c2,'3');
F11(c1,c2,'4'); F11(c1,c2,'5'); F11(c1,c2,'6'); F11(c1,c2,'7');
F11(c1,c2,'8'); F11(c1,c2,'9');
}
void F13(char c1){
F12(c1,'0'); F12(c1,'1'); F12(c1,'2'); F12(c1,'3');
F12(c1,'4'); F12(c1,'5'); F12(c1,'6'); F12(c1,'7');
F12(c1,'8'); F12(c1,'9');
}
void main(){
puts(" 1"); puts(" 2"); puts(" 3"); puts(" 4"); puts(" 5");
puts(" 6"); puts(" 7"); puts(" 8"); puts(" 9");
F11(' ',' ','1'); F11(' ',' ','2'); F11(' ',' ','3');
F11(' ',' ','4'); F11(' ',' ','5'); F11(' ',' ','6'); F11(' ',' ','7');
F11(' ',' ','8'); F11(' ',' ','9');
F12(' ','1'); F12(' ','2'); F12(' ','3');
F12(' ','4'); F12(' ','5'); F12(' ','6'); F12(' ','7');
F12(' ','8'); F12(' ','9');
F13('1'); F13('2'); F13('3');
F13('4'); F13('5'); F13('6'); F13('7');
F13('8'); F13('9');
puts("10000");
}Правда, здесь сравнения могут спрятаться в puts, но можно избавиться и от них.
if и switch — это сравнения.Смотря что считать сравнением. Наличие оператора сравнения в коде? Любой cmp после компиляции? jne/jnz?
switch — это не обязательно сравнение. Если он без default, и компилятору каким-то образом объяснить, что никаких значений, кроме перечисленных быть не может, то он может быть реализован, как переход по адресу, который берётся из массива.
2 2 = 1002
К сожалению, символы «1» и «0» не относятся ни к двойкам, ни к знакам математических операций. Задача не решена.
Посмотрите ответ на эту задачу в самом посте. Найдете те же «1» и «0» и даже "=", что и у меня.
Запись «100 = » в формулировке ответа в самом посте относится не к «значимой» части ответа, а к «описательной» (воде, то бишь). Разница такая же, как между ответами «40» и «в корзине было 40 яблок» — ее можно опустить без потери правильности ответа. В оставшейся «значимой» части лишних символов нет. В вашем случае для того, чтобы признать ответ верным, необходимо иметь обе части равенства, то есть они обе «значимы», и уже в них появляются лишние символы — ответ неверен.
Впрочем, мой косяк. Автор не задал обязательного условия системы счисления числа «100», а значит, что ваш ответ «2 в степени 2» не только является решением, но и использует меньшее количество двоек. Как говорится, де-юре вы правы.
Впрочем, мой косяк. Автор не задал обязательного условия системы счисления числа «100», а значит, что ваш ответ «2 в степени 2» не только является решением, но и использует меньшее количество двоек. Как говорится, де-юре вы правы.
Да тут просто обычная «хитрость», которая хорошо работает, если кто-то уже написал на листочке (или на доске)
и просит записать тремя двойками.
Ответ про хитрое сочетание корней и логарифмов я уже однажды находил, и он мне не нравится, если честно.
100 =
и просит записать тремя двойками.
Ответ про хитрое сочетание корней и логарифмов я уже однажды находил, и он мне не нравится, если честно.
Если пойти на другую хитрость (опустить «ноль целых» в десятичной дроби), то ниже предложили еще одно решение, более изящное, чем корни и логарифмы.
(2e2/2)
Понимаю, что экспоненциальная запись != математическая операция, а скорее математическая нотация, но все же
Понимаю, что экспоненциальная запись != математическая операция, а скорее математическая нотация, но все же
Тоже пришёл к такому решению. Решение, приведённое автором — полная херня. К тому же противоречит цели:
вспоминать задачки, которые были бы понятны и интересны всем
… нужно вспоминать задачки, которые были бы понятны и интересны всем, поэтому какие-нибудь клёвые математические задачки отпадают
Как с помощью трёх двоек и любых знаков математических операций записать число 100?
У этого хорошо изученного явления даже красивое название есть:
Проклятие знания
Блин, как в поезде не еду, то купе милиционеров, едущих на стрельбы в мск, то строители, то военные гуляют, то мама с ребенком, то бабушки. Немогу представить ситуацию чтобы решать задачки, кроме как втихаря для себя :)
А за разминку для ума спасибо :)
А за разминку для ума спасибо :)
Поэтому я еду в плацкарте… Честно, именно поэтому! :)
Вот серьезно, в плацкарте порядок и спокойствие — в разы выше, чем в купе. Постоянно ходит полиция, которая шугает пьянчуг (и которую они боятся таки). Всякие родители с детьми чаще едут в купе — орущих детей и орущих на них родителей по-минимуму. Бабушки в плацкартах обычно все боятся за себя (хотя странно, в плацкарте безопаснее) и поэтому все зажатые сидят, не пристают в основном. Итог — хочешь выбирай себе собеседника, хочешь предоставь время сам себе.
Тоже езжу только на плацкарте, намного больше нравится.
Тоже езжу только на плацкарте, намного больше нравится.
А вот у меня например ноги не входят на койку в плацкарте. Калачиком спать? :) Поэтому всегда требую, чтобы заказывали билет в купе.
Да, в купе полка будет чуть длиннее. Но там вроде как разница около 5-10 см, они действительно настолько погоду делают? А если человек еще длиннее окажется, тогда вообще упрется в стенку ногами и даже свесить ноги будет невозможно (хоть это и не принято в плацкарте).
Так то я тоже длиннее, чем верхняя полна в плацкарте, но для меня эта проблема не актуальна, я на спине спать вообще не умею, только на боку. А тут уж самое удобное, ноги чуть поджать :))
Так то я тоже длиннее, чем верхняя полна в плацкарте, но для меня эта проблема не актуальна, я на спине спать вообще не умею, только на боку. А тут уж самое удобное, ноги чуть поджать :))
С милиционерами можно играть в «складывание в трехлитровую банку». Много нового узнаешь :)
Задачу №5 про черепах не понял. Средняя черепаха ползет в обратную сторону же.
1. Написать программу, которая печатает числа от 1 до 10000 не используя никаких сравнений.
<?php
echo implode(',', range(1,10000));
2. В массиве интов все числа кроме одного повторяются два раза. Как за O(1) памяти и O(n) операций найти это число-одиночку?
<?php
$counts = array_count_values($input);
echo array_flip($counts)[1];
Написать программу, которая печатает числа от 1 до 10000 не используя никаких сравнений.
Строго говоря, эта программа печатает числа от 1 до 10000.
for (unsigned int i=0;;i++){
printf("%d, ",(i % 10000) + 1);
}
Чуть выше уже привели такой пример.
Вот еще вариант, не такой читерский:
Вот еще вариант, не такой читерский:
#define LOW 1
#define HIGH 10
void print(int i){
printf("%d\n", i);
}
void done(int i){
exit(0);
}
int main(int argc, char* argv[]) {
void (*func[2])(int);
func[0] = print;
func[1] = done;
for (unsigned int i = LOW;; i++){
func[i / (HIGH+1)](i);
}
}
можно и вообще без цикла
#include <stdio.h>
typedef void (*F)(int);
F f[2];
inline void next(int i){
printf("%d\n", i++);
f[i/10001](i);
}
inline void end(int i){
return;
}
int main(void){
f[0] = next;
f[1] = end;
next(1);
return 0;
}
завуалированная рекурсия…
Ну, да. Тогда так.
int main(void){
int i = 1;
void *f[2];
f[0] = &&next;
f[1] = &&end;
next:
printf("%d\n", i++);
goto *f[i/11];
end: return 0;
}
теперь цикл завуалирован…
вообще говоря, без сравнений это не скомпилировать…
вообще говоря, без сравнений это не скомпилировать…
мне больше нравится:
или
#include <iostream>
using namespace std;
class A
{
static int i;
public:
A() { cout << ++i << endl; }
};
int A::i = 0;
int main()
{
A array[1000];
return 0;
}
или
echo implode("\n", range(1, 1000));
Первое — очень хорошо! А по поводу завуалированных циклов и рекурсий — они в моих примерах, по-моему, не завуалированы, а вообще практически в чистом виде написаны.
ещё экзотика — рекурсия на генериках:
Хвостовая(даже не знаю, вывернется в цикл?):
Скрытый текст
#include <iostream>
template <int k> void foo(){
foo<k-1>();
std::cout << k << std::endl;
}
template <> void foo<0> () {}
int main () {
foo<1000>();
return 0;
}
Хвостовая(даже не знаю, вывернется в цикл?):
Скрытый текст
#include <iostream>
template <int k> void foo(){
std::cout << k << std::endl;
foo<k+1>();
}
template <> void foo<1001> () {}
int main () {
foo<1>();
return 0;
}
Подобное в одном из первых комментариев предложили :) По поводу второго примера, думаю, что зависит от компилятора
кстати, вариант с конструктором по умолчанию (как и мой вариант ниже) не проходит по памяти O(1)
Если задача не N, а именно 10000:
Псевдокод
f(a) -> echo a
f(1)
f(2)
...
f(10000)
Более оптимальное, с точки зрения размера программы
foo() -> echo ++i
f10(f) -> f(); f(); f(); f(); f(); f(); f(); f(); f(); f();
f100(f) -> f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f);
f1000(f) -> f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f);
f10000(f) -> f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f);
f10000(foo);
f10(f) -> f(); f(); f(); f(); f(); f(); f(); f(); f(); f();
f100(f) -> f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f); f10(f);
f1000(f) -> f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f); f100(f);
f10000(f) -> f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f); f1000(f);
f10000(foo);
а вообще, самое короткое, что придумалось, (с некоторыми оговорками к формату вывода), это вот
1:10000
вообще говоря, без сравнений это не скомпилировать…
Там сравнения только в printf / cout. В теле программы сравнений нет.
Нельзя, несложно придумать подходящий инвариант.
Как же я обожаю советские учебники с формулировками «задачу доказательства мы оставляем читателю»…
Ответ на первый вопрос был неожиданным. Он показал мне какое я ничтожество.
Поверьте, не вам одному=)
А по мне, все жуткий боян.
Потому что у меня в детстве была вот такая книга:
Е. Я. Гик — Занимательные математические игры
Потому что у меня в детстве была вот такая книга:
Е. Я. Гик — Занимательные математические игры
Race condition же!
А я предположил зеркало позади третьей.
А чем не подходит такое решение?..
Оу! И правда решение :)
Задачи писал как знал, сейчас посмотрел в интернете, там третья черепаха говорит: «Впереди меня две черепахи и сзади две черепахи».
Задачи писал как знал, сейчас посмотрел в интернете, там третья черепаха говорит: «Впереди меня две черепахи и сзади две черепахи».
Чорд, а я вначале подумал: «Ух-ты, СТО, световые конусы и относительность понятий „спереди/сзади“...»
В формулировке первой задачи сказано, что можно использовать математические операции. Я думал, что функции использовать нельзя. Поэтому придумал такое решение:
Задача 1
Эх, вторую программисткую задачку мне дали на собеседовании — и я, увы, забыл про XOR. :(
Как известно, из черепах умеют разговаривать только черепашки-ниндзя. Их всегда четверо, значит за тремя ползёт ещё один.
Другой вид занимательных задачек — данетки (задачки-ситуации), где отгадывающие должны понять логику предложенной ситуации, получая информацию от ведущего закрытыми вопросами (да/нет).
Классический пример: человек заходит в бар, просит стакан воды, бармен наставляет на него ружье, человек говорит бармену «спасибо» и уходит. Объясните действия персонажей.
Классический пример: человек заходит в бар, просит стакан воды, бармен наставляет на него ружье, человек говорит бармену «спасибо» и уходит. Объясните действия персонажей.
var a = new Array(10000), i = 1;
while (a.length) {
console.log(i++);
a.pop();
}
JavaScript
while (a.length) {
console.log(i++);
a.pop();
}
JavaScript
Разделим круг на шесть секторов, запишем в секторы числа 1, 0, 1, 0, 0, 0. Разрешается прибавлять по единице к двум соседним числам. Можно ли сделать все числа одинаковыми?По 3-ей не понял. Если секторов 6, то поочередное добалвение 1 к соседним элементам 1, 3 -5 даст во всем круге значение 2.
101000
111001
121101
122111
122212
222222
Если сектора пронумеровать 1, 2, 3, 4, 5, 6 по часовой стрелке, то соседними будут 1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 1. А у вас какое-то другое отношение соседства :)
Еще можно прибавлять к противоположным — 1+4, 2+5, 3+6. Результат тот же самый.
Ага. Задачу можно решить, если понять так: Делим круг на 6 секторов. <...> разрешается прибавлять по 1 к двум соседним числам <сектора>.
Я тоже задачу понял, как автор комента, тоже решил и полез уже гневный комент писать.
Вы явно не к соседним числам прибавляете.
1.Где часы никогда не врут? При этом их не поверяют и не калибруют.
2. Есть некий мир (планета), жители которой живут в 2D пространстве. Каким образом им можно доказать, что они живут на шаре (т.е. в 3D пространстве)?
3. Инопланетяне вторглись на Землю. Захватили 10 жителей планеты и закрыли в одной комнате. Через сутки они поставили их друг за другом на ступеньки одной лестницы. На каждом из людей была шапка либо красного, либо синего цвета. Человек, стоящий на самой верхней ступеньке должен сказать одно слово (либо «красный», либо «синий»). Если он угадал — то он остается жить, если нет — будет уничтожен. Затем слово говорит нижестоящий и так далее до человека, стоящего на самой нижней ступеньке. Если хотя бы 6-ро из них выживут — то инопланетяне улетят и никого больше не тронут, если нет — уничтожат Землю? Что нужно делать этим людям?
Ответ
Северный и Южный полюса. В каком то часовом поясе всегда будет время, как на часах.
2. Есть некий мир (планета), жители которой живут в 2D пространстве. Каким образом им можно доказать, что они живут на шаре (т.е. в 3D пространстве)?
Ответ
Нужно попросить одного из них перемещаться по кругу, раз за разом увеличивая диаметр круга. Когда житель этого мира пересечет экватор — диаметр окружностей начнет уменьшаться.
3. Инопланетяне вторглись на Землю. Захватили 10 жителей планеты и закрыли в одной комнате. Через сутки они поставили их друг за другом на ступеньки одной лестницы. На каждом из людей была шапка либо красного, либо синего цвета. Человек, стоящий на самой верхней ступеньке должен сказать одно слово (либо «красный», либо «синий»). Если он угадал — то он остается жить, если нет — будет уничтожен. Затем слово говорит нижестоящий и так далее до человека, стоящего на самой нижней ступеньке. Если хотя бы 6-ро из них выживут — то инопланетяне улетят и никого больше не тронут, если нет — уничтожат Землю? Что нужно делать этим людям?
Ответ
Умышленно не напишу. Не отчаивайтесь, ответ очевиден.
Вот тоже занимательно.
Вроде неплохие задачки, только условия некорректны/многозначны.
Астрономическое-то время точно совпадёт где-нибудь, а вот поясное — вряд ли (раз уж вы заговорили про часовые пояса).
Всё-таки «на шаре» и «в 3D пространстве» — разные вещи.
Точно диаметр начнёт уменьшаться? Это зависит от того, как его мерять — если из исходной точки, то он будет увеличиваться (ведь так и написано — «раз за разом увеличивая диаметр круга»), а если из противоположной на шаре — то что тогда вообще доказывать? Далее предполагаю, что имели в виду длину.
Ваш способ ничего не доказывает про шар — длина начнёт уменьшаться и на эллипсоиде, к примеру, а также на многих других геометрических телах. Даже конкретной зависимости длины от радиуса, построенной по конечному или счётному множеству окружностей не хватит. На первый взгляд кажется, что хватит (несчётного) перебора всех радиусов с одним центром, но тут нужно смотреть… Ну или другой способ выбирать :)
По третьей — не понятно, кто из них кого видеть может. Если тот, кто говорит первым видит всех остальных, второй — всех начиная с третьего и т.д., то решение действительно очевидно. Только вот почему только 6 должны выжить, когда можно 9? Или это доброта инопланетян? :)
Северный и Южный полюса. В каком то часовом поясе всегда будет время, как на часах.
Астрономическое-то время точно совпадёт где-нибудь, а вот поясное — вряд ли (раз уж вы заговорили про часовые пояса).
2. Есть некий мир (планета), жители которой живут в 2D пространстве. Каким образом им можно доказать, что они живут на шаре (т.е. в 3D пространстве)?
Всё-таки «на шаре» и «в 3D пространстве» — разные вещи.
Нужно попросить одного из них перемещаться по кругу, раз за разом увеличивая диаметр круга. Когда житель этого мира пересечет экватор — диаметр окружностей начнет уменьшаться.
Точно диаметр начнёт уменьшаться? Это зависит от того, как его мерять — если из исходной точки, то он будет увеличиваться (ведь так и написано — «раз за разом увеличивая диаметр круга»), а если из противоположной на шаре — то что тогда вообще доказывать? Далее предполагаю, что имели в виду длину.
Ваш способ ничего не доказывает про шар — длина начнёт уменьшаться и на эллипсоиде, к примеру, а также на многих других геометрических телах. Даже конкретной зависимости длины от радиуса, построенной по конечному или счётному множеству окружностей не хватит. На первый взгляд кажется, что хватит (несчётного) перебора всех радиусов с одним центром, но тут нужно смотреть… Ну или другой способ выбирать :)
По третьей — не понятно, кто из них кого видеть может. Если тот, кто говорит первым видит всех остальных, второй — всех начиная с третьего и т.д., то решение действительно очевидно. Только вот почему только 6 должны выжить, когда можно 9? Или это доброта инопланетян? :)
Да, вспомнилось примерно на тему второй задачи — вопрос на math.stackexchange: как отличить сферу от тора, перемещаясь только по поверхности.
Да, возможно где то напартачил с формулировками. Уж простите.
По поводу 3-го, то да… инопланетяне в некотором смысле гуманисты. Кроме того существует другое решение, где выживают именно 6-ро. ))
По поводу 3-го, то да… инопланетяне в некотором смысле гуманисты. Кроме того существует другое решение, где выживают именно 6-ро. ))
Подскажите пожалуйста, как вы спасли 9 человек. Интересно стало, ничего на ум не пришло, чтобы сразу 9 спасти.
В условии, кстати, не написано, что именно должны отгадать люди :) Будем считать, что имелся в виду цвет своей шапки.
Обозначим красный за 0, синий за 1. Первый считает сумму S_1, которую видит на других, и говорит S_1 mod 2 — то есть, возможно, ошибается с цветом своей шапки. Второй, услышав это, считает аналогично сумму тех, кого он видит, S_2. Если S_1 == S_2 (mod 2), то цвет второго это 0 (красный), иначе синий. Далее, третий знает S_1 mod 2 (это сказал 1й) и S_2 mod 2 (из ответа 2го). Аналогично, он считает S_3, ну и далее то же самое: каждый i-й знает S_(i-1) и S_i по модулю 2, и точно говорит свой цвет.
Вроде правильно понял условие, и ничего не напутал :)
Обозначим красный за 0, синий за 1. Первый считает сумму S_1, которую видит на других, и говорит S_1 mod 2 — то есть, возможно, ошибается с цветом своей шапки. Второй, услышав это, считает аналогично сумму тех, кого он видит, S_2. Если S_1 == S_2 (mod 2), то цвет второго это 0 (красный), иначе синий. Далее, третий знает S_1 mod 2 (это сказал 1й) и S_2 mod 2 (из ответа 2го). Аналогично, он считает S_3, ну и далее то же самое: каждый i-й знает S_(i-1) и S_i по модулю 2, и точно говорит свой цвет.
Вроде правильно понял условие, и ничего не напутал :)
Пожалуй, переведу с программерского :)
Первый считает, шапок какого цвета он видит перед собой в нечётном количестве (или в чётном — как заранее договорились) и называет этот цвет. Допустим, красный. С первым как повезёт — может и угадать. Второй тоже считает шапки впередистоящих. Если красных насчитал нечётное количество, то, значит, на нём синяя шапка, и наоборот. Следующие также считают шапки впередистоящих и учитывают предыдущие ответы. И т.д.
Первый считает, шапок какого цвета он видит перед собой в нечётном количестве (или в чётном — как заранее договорились) и называет этот цвет. Допустим, красный. С первым как повезёт — может и угадать. Второй тоже считает шапки впередистоящих. Если красных насчитал нечётное количество, то, значит, на нём синяя шапка, и наоборот. Следующие также считают шапки впередистоящих и учитывают предыдущие ответы. И т.д.
Да, совершенно верно. Поздравляю.
Чушь. Меньше надо в алгоритмах копаться.
1) 9 должны назвать цвет шапки самого нижнего.
2) Шапки вообще не при делах. 9 нижних должны просто тупо повторить цвет за верхним)))
1) 9 должны назвать цвет шапки самого нижнего.
2) Шапки вообще не при делах. 9 нижних должны просто тупо повторить цвет за верхним)))
Нет. Просто нет.
Это вы два варианта решения предъявили? Или что? Я немного не понял.
В случае, если я понял вас правильно:
1) Если 9 назовут цвет самого нижнего, они все девять и помрут, если, например, все они синие, а последний красный.
2) Если они будут повторять цвет за верхним, то тоже все умрут, потому что они будут повторять один и тот же цвет, который и назвал самый первый.
В случае, если я понял вас правильно:
1) Если 9 назовут цвет самого нижнего, они все девять и помрут, если, например, все они синие, а последний красный.
2) Если они будут повторять цвет за верхним, то тоже все умрут, потому что они будут повторять один и тот же цвет, который и назвал самый первый.
удалил
7. Самолет пролетел 100 километров на юг, затем 100 километров на восток, а затем 100 километров на север. В итоге самолёт оказался в исходной точке. Откуда он мог вылететь?
Таких точек две.
Намного больше :) В идеальном случае точечного самолёта — бесконечно много (счётно).
И да, буквально на днях на Хабре было.
8) Путешественник прошёл один километр на юг, затем один километр на запад, а после один километр на север и вернулся в исходную точку. Сколько существует таких мест на земле? Подсказка: больше одного…
А как же наматывание квадратов вокруг экватора?
В Гаражи лучше всего играть со спичками. В разных схемах из 10-15 спичек игрокам интереснее проверять свои теории, что же такое этот «гараж». По крайней мере я, только с ними показываю эту игру. Удачная игра может продолжаться не 10-15 минут, а часа 2-3 и доставить много веселья окружающим. Главное, что бы потом тебя не поймали, потому что люди очень эмоционально в неё втягиваются. Особенно, если менее умные догадываются раньше и начинают называть правильное количество гаражей.
Уточню, гаражей может быть от 0 до 10.
Уточню, гаражей может быть от 0 до 10.
Используя трёх людей, мы доводили число гаражей до 30 :)
Ещё всегда на ура идёт игра «Бэни-бэни-бэни-бэни-упс», кстати.
А что это за игра?
Хм. это очень просто показать, но сложно объяснить. Но попытаюсь. Указательным пальцем одной руки нужно по очереди касаться кончика мизинца, безымянного пальца, среднего, указательного, впадину между указательным и большим пальцем, большой палец, потом снова впадину, потом указательный, потом средний, потом безымянный и мизинец. При это при касании пальца говорится «бэни», а при касании впадины — «упс». После этого просим других людей повторить всё тоже самое. При этом перед тем как попросить повторить, пальцы нужно незаметно сложить в «замок». Как правило человек повторяет только то, что было со словами, а руки в замок не складывает.
Когда уже несколько человек огадывают это, они могут одновременно начать показывать, до тех пор пока до всех не дойдёт.
Какое-то сложное объяснение получилось, но на деле также весело как и гаражи.
Когда уже несколько человек огадывают это, они могут одновременно начать показывать, до тех пор пока до всех не дойдёт.
Какое-то сложное объяснение получилось, но на деле также весело как и гаражи.
Не надо в гаражи играть со спичками, у нас на побережье Финского залива пацаны играли — подожгли за гаражами заросли сухого камыша, три гаража сгорело. Не надо…
Если путешествующих >4, замечательно идет игра контакт — для неё вообще ничего не нужно, кроме мозгов.
Если можно использовать e, то все ещё проще:
ln(e) + ln(e) +… 100 раз = 100
Если честно, понравилось толко с десятичной записью, но это уже больше похоже на программирование, чем на математику
ln(e) + ln(e) +… 100 раз = 100
Если честно, понравилось толко с десятичной записью, но это уже больше похоже на программирование, чем на математику
8. К стене прислонена лестница.… По какой траектории двигался котёнок?Сомневаюсь, что это именно окружность. Какая-то кривая второго порядка, возможно гипербола.
То, что ответом является кусок окружности, догадываются все...
Проведите эксперимент с карандашом и листом бумаги :)
Мне кажется, яснее видно, если рассматривать «наоборот», т.е. угол с точки зрения котёнка посередине лестницы. Построим окружность с лестницей в качестве диаметра, тогда котёнок — её центр. Далее, есть прямой угол, стороны которого всегда проходят через концы диаметра окружности — следовательно, его вершина в любом случае находится на нашей окружности. Это означает, что угол описывает дугу окружности вокруг котёнка — но тогда, очевидно, верно и обратное.
Подходящая картинка (не моя)
Программистская задача №4 (про YES и NO): про ваш вариант не подумал, первым пришло в голову альтернативное решение.
struct V {};
bool operator== (const V& a, const V&b) { return false; }
void main() {
V v;
if (v == v) {
std::cout << «YES»;
} else {
std::cout << «NO»;
}
}
struct V {};
bool operator== (const V& a, const V&b) { return false; }
void main() {
V v;
if (v == v) {
std::cout << «YES»;
} else {
std::cout << «NO»;
}
}
У кого-то есть идеи по поводу 9й задачи с коробками и предметами?
1. Если у вас есть листочек бумаги и две ручки, то можно сыграть в старый добрый морской бой. Это одна из тех игр, которые никогда не надоедают.Надоедают, если знаешь оптимальную стратегию.
Перестал читать после второй задачи
Убил ответ «нельзя. несложно придумать пример». Пример-то не сложно, а по задаче надо доказать, что любой пример не подходит.
Интересно автор понимает разницу между квантором существования и квантором общности?
Убил ответ «нельзя. несложно придумать пример». Пример-то не сложно, а по задаче надо доказать, что любой пример не подходит.
Интересно автор понимает разницу между квантором существования и квантором общности?
Там не пример несложно придумать, а инвариант :) Читайте внимательнее.
что это вообще такое? контрпример? и как он выглядит? :)
2 задача по моему решается так:
2 задача по моему решается так:
Скрытый текст
отпилив A1 и H8 мы остаёмся с доской, на которой 32 белых и 30 черных клеток. Каждая доминошка занимает одновременно белую и черную, следовательно нам необходимо равное соотношение цветов…
Да вот следующая третья задача, как раз инвариант второй.
Инвариант, это некоторое условие которое остаётся верным после преобразования. Например, в задаче с доской инвариантом будет разность числа белых клеток и чёрных. Так как в самом начале эта разность равна двум, а после покрытия любым числом доминошек — тоже равна двум. Но так как у пустой доски инвариант этот равен 0, то, следовательно, мы не сможем придумать нужное замощение.
В задаче про сектора инвариантом будет разность суммы чисел в первом, третьем и пятом секторах, и суммы чисел во втором, четвёртом и шестом секторах.
https://ru.wikipedia.org/wiki/Задачи_на_инварианты
В задаче про сектора инвариантом будет разность суммы чисел в первом, третьем и пятом секторах, и суммы чисел во втором, четвёртом и шестом секторах.
https://ru.wikipedia.org/wiki/Задачи_на_инварианты
Автор защитил кандидатскую по 01.01.06 и понимает разницу между квантором существования и квантором общности (:
1. Написать программу, которая печатает числа от 1 до 10000 не используя никаких сравнений.
С формулировкой можно очень долго играться.
Не все, но в условие про это и не сказано: print( random(1,10000) );
Можно еще файл прочесть с этими самыми числами от 1 до 10000 их вывести.
А вообще странно видеть такую формулировку в задачах для «программиста». Люди годами вешаются от таких описаний, а вы им предлагаете их решать для развлечения, да вы садист ))
С формулировкой можно очень долго играться.
Не все, но в условие про это и не сказано: print( random(1,10000) );
Можно еще файл прочесть с этими самыми числами от 1 до 10000 их вывести.
А вообще странно видеть такую формулировку в задачах для «программиста». Люди годами вешаются от таких описаний, а вы им предлагаете их решать для развлечения, да вы садист ))
Постановка задачи простая и понятная…
Всегда найдутся уникумы, которым условие «не нравится»:
«не используя сравнений» === «линейный алгоритм»
следовательно единственно верное решение:
безусловные переходы/вызовы подпрограмм позволяют нам значительно уменьшить число строк: вот
Всё остальное — попытки спрятать сравнение/цикл или клоунада с «про это и не сказано»
Всегда найдутся уникумы, которым условие «не нравится»:
— Составить число 100 из трёх двоек и мат.операций.
— 22*2 + 56
«не используя сравнений» === «линейный алгоритм»
следовательно единственно верное решение:
int i = 0;
printf("%d\n", ++i); // x10000 раз
безусловные переходы/вызовы подпрограмм позволяют нам значительно уменьшить число строк: вот
Всё остальное — попытки спрятать сравнение/цикл или клоунада с «про это и не сказано»
Просто мы с вами разные люди, вы решаете задачи теми способами которые вам уже известны.
Вы вот например не захотели написать свой язык, в котором нету сравнений, и в котором есть только один оператор, выводящий на экран числа от 1 до 10000.
И уже на нем написать эту программу в однин оператор: print1to10000.
Погуглите на тему «Измерение высоты здания с помощью барометра», и вы поймете, что мир намного интереснее.
Вы вот например не захотели написать свой язык, в котором нету сравнений, и в котором есть только один оператор, выводящий на экран числа от 1 до 10000.
И уже на нем написать эту программу в однин оператор: print1to10000.
Погуглите на тему «Измерение высоты здания с помощью барометра», и вы поймете, что мир намного интереснее.
Вот первое предложение правда обидно было :)
А вот print1to10000 исключительно неинтересное решение…
Ещё и гуглить баяны посылаете…
Про рандом решение в принципе неплохое, если бы не была столь очевидна и навязчива неверная трактовка условия
А вот print1to10000 исключительно неинтересное решение…
— Я тут новую задачку нашёл, слушай — "...."
— Я решил! — «solve();»
Ещё и гуглить баяны посылаете…
Про рандом решение в принципе неплохое, если бы не была столь очевидна и навязчива неверная трактовка условия
Цикл формально не запрещён. И решение с переходом по табличке (если, конечно, язык действительно поддерживает «адрес метки» и если вместо f[i/11] написать f[i/10001]) действительно можно скомпилировать в код без сравнений:
Как-то так
push bp
mov bp,sp
push 1
_1:
inc word ptr [bp-4]
push [bp-4]
push str_format
call _printf
add sp,4
mov ax,[bp-4]
cwd
mov cx,10001
idiv cx
add ax,ax
mov bx,ax
jmp [jtbl+bx]
_2:
pop ax
pop bp
ret
str_format: db 37,100,10,0
jtbl: dw _1,_2
Формулировки короткие, чтобы была видна суть задачи, если что-то непонятно, меня всегда спросят и я уточню, как я понимаю условие.
И вообще как где-то писал Арнольд: «Дело в том, что я правильно представляю себе степень идиотизма составителей этих задач» :)
И вообще как где-то писал Арнольд: «Дело в том, что я правильно представляю себе степень идиотизма составителей этих задач» :)
4. Огурец на 90 процентов состоит из воды, а человек — на 70 процентов. На сколько процентов человек является огурцом?
Да, кажется эту задачу мне задавали лет 15 назад, когда я пытался поступить в ФМШ (НГУ) после 9-го класса. Я не решил. Видать — завалили :) (через год поступил, но это совсем другая история).
Попробую порассуждать. Что получится, то получится. Не факт конечно что верно, но ведь интересно! :)
Предположим, что пересечение только по воде.
В огурце 100% — 90% = 10% самого огурца. По тем же соображениям в человеке 30% «человека» (остальное вода). То есть выходит что на что-то из диапазона 0 — 70% человек — огурец. Но, огурец сам не на 100% огурец, а лишь на 10%, следовательно 70% * 10% = 7% огурца в воде человека. Но мы знаем что 70% человека — вода, поэтому 7% огурца в воде, это 10% огурца во всем человеке.
Буду рад другим вариантам.
Мой вариант решения.
Все зависит от того, что считать признаком огурца.
Объект является 100% огурцом, если содержит 90% воды и 10% огуречной массы.
Если в этом объекте заменить воду, допустим, на спирт, насколько % можно объект назвать огурцом?
1) Если ответ «100%» (так как он содержит всю огуречную массу), то человек на 0% огурец, так человек не содержит огуречной массы.
2) Если ответ «10%», то значит каждый 1% воды добавляет 1% к огуречности, и человек на 70% огурец.
Все зависит от того, что считать признаком огурца.
Объект является 100% огурцом, если содержит 90% воды и 10% огуречной массы.
Если в этом объекте заменить воду, допустим, на спирт, насколько % можно объект назвать огурцом?
1) Если ответ «100%» (так как он содержит всю огуречную массу), то человек на 0% огурец, так человек не содержит огуречной массы.
2) Если ответ «10%», то значит каждый 1% воды добавляет 1% к огуречности, и человек на 70% огурец.
С точки зрения математики, имеем систему уравнении:
человек = 0,3 человечности + 0,7 воды
огурец = 0,1 огуречности + 0,9 воды.
Система не имеет решения: выразить человека через огурец не получится.
человек = 0,3 человечности + 0,7 воды
огурец = 0,1 огуречности + 0,9 воды.
Система не имеет решения: выразить человека через огурец не получится.
Такая задача и не ставилась
Полностью человека выразить не получится, это очевидно…
Вопрос — насколько человек — огурец…
Далее работает логика progman_rus
Почти работает…
Есть поправки на терминологию
Вот аналогичная задача:
С одной стороны дом на 90% состоит из кирпича, полностью взятого из кучи… значит ответ 90%.
С другой стороны кирпич это только полкучи значит дом состоит из кучи на 45%
Оба ответа верны, в зависимости от вкладываемого в "состоит из кучи" смысла
Полностью человека выразить не получится, это очевидно…
Вопрос — насколько человек — огурец…
Далее работает логика progman_rus
Почти работает…
Есть поправки на терминологию
Вот аналогичная задача:
Есть куча стройматериалов 50%/50% кирпич и щебень
Строим кирпичный дом 9/1 кирпич и раствор
Насколько дом состоит из кучи стройматериалов?..
С одной стороны дом на 90% состоит из кирпича, полностью взятого из кучи… значит ответ 90%.
С другой стороны кирпич это только полкучи значит дом состоит из кучи на 45%
Оба ответа верны, в зависимости от вкладываемого в "состоит из кучи" смысла
пейзаж напоминает окрестности летней Воркуты
знает ли кто-нибудь из хабражителей как с помощью пальцев, яблок, денег и т. п. объяснить, почему при умножении двух отрицательных чисел получается положительное? (Я знаю как это вывести из аксиоматики действительных чисел, но я не знаю какого-либо наглядного объяснения.)
www.youtube.com/watch?v=sFDJUapM6g8 — вот тут очень хорошо расписано.
С помощью чисел понятно, такое объяснение я знаю. Но оно заключается в том, что давайте сделаем так, чтобы остальному не противоречило. Это хорошо, но скучно. Я ищу, где в обычной жизни появляется умножение отрицательных чисел. Причём чтобы это не было притянуто за уши.
Может быть, в формуле s=v*t? Например, вот идёт встречный поезд со скоростью 80 км/ч (v=-80). Где он был час назад (t=-1)? Ответ — в точке, которая находится перед нами на расстоянии s=(-80)*(-1)=+80 км — там же, где мы (v=+80) окажемся через час (t=+1).
Вот это уже интереснее.
Стандартный способ объяснения отрицательных чисел — когда ты кому-то должен денег. Соответственно, -10 будет означать, что ты должен кому-то 10 рублей. (-10) * 5 — означает, что ты должен по 10 рублей пяти кредиторам. Попробуем наделить смыслом умножение (-10) * (-5). Можно считать, что «отрицательные кредиторы» это должники, то есть (-10) * (-5) — это 5 должников, которые должны вернуть по 10 рублей. Этого получается, что всего они должны вернуть +50 рублей.
Но вообще на бытовом уровне одним из множителей очень часто являются «штуки», для которых нормальной отрицательной интерпретации нет, поэтому и нормальной интерпретации для произведения двух отрицательных чисел не будет. Также часто умножают на время — тут вполне подходит пример Mrrl — отрицательное время, как события в прошлом (пример можно разным образом видоизменять, рассматривая любой процесс, зависящий от времени). Ну и еще иногда метры на метры умножают (для получения площадей и объемов) — тут со смысловой нагрузкой отрицательных чисел тоже напряг.
Но вообще на бытовом уровне одним из множителей очень часто являются «штуки», для которых нормальной отрицательной интерпретации нет, поэтому и нормальной интерпретации для произведения двух отрицательных чисел не будет. Также часто умножают на время — тут вполне подходит пример Mrrl — отрицательное время, как события в прошлом (пример можно разным образом видоизменять, рассматривая любой процесс, зависящий от времени). Ну и еще иногда метры на метры умножают (для получения площадей и объемов) — тут со смысловой нагрузкой отрицательных чисел тоже напряг.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Когда больше нечего пить