Микроконтролери и електроника
http://mcu-bg.com/mcu_site/

задачка ;)
http://mcu-bg.com/mcu_site/viewtopic.php?f=3&t=10244		 Страница 1 от 2
Автор:  Н'бабане Гт'муан'га [ Сря Юни 20, 2012 2:05 pm ]
Заглавие:  задачка ;)
Да се извърти цикъл с 256 итерации чрез for() и една еднобайтова променлива. Break в тялото на цикъла и допълнителни променливи не са позволени.

Няма награда - само за умствена гимнастика
:D

За най-напредналите: цикъл с 511 итерации чрез само една еднобайтова променлива
Автор:  CarBeta [ Сря Юни 20, 2012 3:02 pm ]
Заглавие:  Re: задачка ;)
Два цикъла позволени ли са ??
Автор:  ike [ Сря Юни 20, 2012 3:35 pm ]
Заглавие:  Re: задачка ;)
Код:
var i:byte;
begin
  for i := 0 to 255 do
    WriteLn(i);
  readln;
end.

No sweat.
Pascal FTW.
Edit: намерих он-лайн компилатор, ако искате може да тествате кода: http://www.onlinecompiler.net/pascal


Н'бабане Гт'муан'га написа:
За най-напредналите: цикъл с 511 итерации чрез само една еднобайтова променлива

Това мога да го направя и без променлива, само ми трябва микроконтролера да има 8 битов UP/DOWN mode таймер. :)
Автор:  loser [ Сря Юни 20, 2012 7:02 pm ]
Заглавие:  Re: задачка ;)
ако може да се правят по две итерации в тялото на цикъла, за да са точно 511, може нещо такова:

Код:

#include <stdio.h>
#include <stdint.h>

void main(void)
{
uint8_t i = 0;

   for (; printf("итерация %i\n", (i << 1)), i ++, printf(i ? "итерация %i\n" : "край\n", (i << 1) - 1), i; );

}




(тук за 'итерация' се приема работата, която се върши ако се замести печатането на низ 'итерация х' с някаква реална работа; така сметката би трябвало да излиза, и броят на изпълненията да е 511)
Автор:  Пушека [ Сря Юни 20, 2012 10:33 pm ]
Заглавие:  Re: задачка ;)
Два цикъла с една променлива(byte), ако е позволено?? :)
Идеята му е веднъж бори нагоре, после обратно до 0 и излиза...

Прикачени файлове:
code.txt [169 Байта]
281 пъти
Автор:  anrieff [ Сря Юни 20, 2012 11:35 pm ]
Заглавие:  Re: задачка ;)
Ако това е истинското решение на задачата с 511, както го е написал Пушека, да ме прощавате, ама задачата е мега некоректно зададена.

Искате ли една малко по-трудна?

Имате масив с цели числа (могат да са и големи, 32-битови примерно). В него масив, всички числа се срещат точно два пъти, с изключение на едно от тях, което го има само веднъж. Примерно { 3, 188, 55, 55, 3 }.
Търси се кое е самотното. Не се разрешава сортиране. O(N) сложност се гони.
Автор:  ike [ Чет Юни 21, 2012 12:00 am ]
Заглавие:  Re: задачка ;)
Задачата е елементарна. Правиш един масив от 4 300 000 000 бита. Четеш число от масива и гледаш бита, който съответства на числото ако е 0 прибавяш числото към временна променлива, ако е 1 бита, правиш го на 0 и изваждаш числото от временната променлива. накрая временната променлива е със стойност самотното число.
Автор:  anrieff [ Чет Юни 21, 2012 1:30 am ]
Заглавие:  Re: задачка ;)
А, не съм догледал, числата били 64-битови :D
Автор:  Reader [ Чет Юни 21, 2012 8:33 am ]
Заглавие:  Re: задачка ;)
anrieff написа:
Търси се кое е самотното. Не се разрешава сортиране. O(N) сложност се гони.

Хм, не мога да си представя какъв трик може да се приложи, че да постигнеш O(N). В най-добрия случай виждам O(N^2/2).
Автор:  anrieff [ Чет Юни 21, 2012 10:44 am ]
Заглавие:  Re: задачка ;)
Дори само със сортиране вече е O(N logN), но, както казах, има и по-добро решение :)
Автор:  Н'бабане Гт'муан'га [ Чет Юни 21, 2012 10:52 am ]
Заглавие:  Re: задачка ;)
anrieff написа:
Ако това е истинското решение на задачата с 511, както го е написал Пушека, да ме прощавате, ама задачата е мега некоректно зададена.

Искате ли една малко по-трудна?

Имате масив с цели числа (могат да са и големи, 32-битови примерно). В него масив, всички числа се срещат точно два пъти, с изключение на едно от тях, което го има само веднъж. Примерно { 3, 188, 55, 55, 3 }.
Търси се кое е самотното. Не се разрешава сортиране. O(N) сложност се гони.


Абе аз си мислех, че като съм писал for() всеки ще разбере, че става дума за C-код. На Паскал и Бейсик и бабите могат да го направят това. Освен това съм писал "итерации" т.е. не е казахо, че променливата трябва да се извърти последователно. Е, след тая подсказка... :wink:

А това с масива... не съм го пробвал, само като идея - ако извъртиш целия масив и правиш XOR на всички числа в него, би трябвало накрая да остане това, което е самотно, тъй като другите ще са се нулирали побитово.
Ето в примера, който си дал, резултатите след всеки XOR: 0 (начално), 3, 191, 136, 191, 188 (краен резултат)
Автор:  Reader [ Чет Юни 21, 2012 11:21 am ]
Заглавие:  Re: задачка ;)
Н'бабане Гт'муан'га написа:
… ако извъртиш целия масив и правиш XOR на всички числа в него, би трябвало накрая да остане това, което е самотно, тъй като другите ще са се нулирали побитово.

Мда-а-а… :oops:
Автор:  t_i_t_o [ Чет Юни 21, 2012 4:23 pm ]
Заглавие:  Re: задачка ;)
uint8_t ii;

for (ii = 0; ii; ii++)
do_something();

???
Автор:  ike [ Чет Юни 21, 2012 4:34 pm ]
Заглавие:  Re: задачка ;)
t_i_t_o написа:
uint8_t ii;

for (ii = 0; ii; ii++)
do_something();

???

Това тества ли го? Ако да кажи с кой компилатор.
Автор:  t_i_t_o [ Чет Юни 21, 2012 4:52 pm ]
Заглавие:  Re: задачка ;)
Мда няма да стане щото условието се проверява в началото а не в края... с do-while ще стане...
Страница 1 от 2 Часовете са според зоната UTC + 2 часа [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/