301 Востаннє редагувалося Vo_Vik (19.07.2018 19:00:22)

Re: Цікаві задачі

00101110
1, 2, 5, 3,  7,  6, 4, 0
Нє?

Подякували: leofun01, ReAl, Yola, 0x9111A4

302 Востаннє редагувалося leofun01 (19.07.2018 19:32:34)

Re: Цікаві задачі

morgot написав:

leofun01, я щось не розумію, як можна не використовувати стандартну функцію виводу 2 або більше разів в коді. І вивести ці числа, за 1 раз. Де їх тоді зберігати, якщо умовою задачі массиви заборонені,а змінні не більше 8 біт?

@Vo_Vik дав правильну підказку :

Vo_Vik написав:

00101110
1, 2, 5, 3,  7,  6, 4, 0
Нє?

Та що там підказку ... Можна сказати Vo_Vik розв'язав задачу.


Yola написав:
Для 7:

char spreadLSB(char in) {
    in = in & 1;
    in = in | (in << 1) | (in << 2) | (in << 3) | (in << 4) | (in << 5) | (in << 6) | (in << 7);
    return in;
}

void leofun() {
    bool curr1;
    bool prev0 = true;
    unsigned char i = (unsigned char)-1;
    char out = 0;
    while (out != 7) {
        out = 0;
        for (int j = 1; j < 8; ++j) {// цей цикл лише для читності коду, можна розгорнути в 7 блоків
            curr1 = i & (1 << j);
            bool useIt = curr1 && prev0;
            out |= spreadLSB(useIt) & j;
            prev0 = !curr1;
        }
        std::cout << (int)out << " ";
        i = i << 1;
    }
}
Консоль написав:

1 0 2 3 4 5 6 7

Для 15:
Замінюємо char на short, 7 на 15 і 8 на 16.

void leofun() {
    bool curr1;
    bool prev0 = true;
    unsigned short i = (unsigned short)-1;
    short out = 0;
    while (out != 15) {
        out = 0;
        for (int j = 1; j < 16; ++j) {
            curr1 = i & (1 << j);
            bool useIt = curr1 && prev0;
            out |= spreadLSB(useIt) & j;
            prev0 = !curr1;
        }
        std::cout << (int)out << " ";
        i = i << 1;
    }
}
Консоль написав:

1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Очевидно, що це не те, що хтів пан leofun01, бо дзен теорії автоматів для мене залишається непізнаним.

Ого.. Цікавий розв'язок. Але ++j не дозволяється.
Це задача із тих, про які кажуть "розв'язується в 3 рядки коду".


koala написав:

А яке з правил забороняє робити

cout<<0<<endl<<1<<endl<<2<<endl...

?

Хороше питання. Про потоковий вивід я не подумав. Але будемо вважати, що це багато викликів виводу.

upd: Ладно, <<endl можете використовувати скільки хочете, <<endl не рахуємо.

303

Re: Цікаві задачі

Vo_Vik написав:

00101110
1, 2, 5, 3,  7,  6, 4, 0
Нє?

Красиво!

printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");

304

Re: Цікаві задачі

leofun01 написав:
koala написав:

А яке з правил забороняє робити

cout<<0<<endl<<1<<endl<<2<<endl...

?

Хороше питання. Про потоковий вивід я не подумав. Але будемо вважати, що це багато викликів виводу.

upd: Ладно, <<endl можете використовувати скільки хочете, <<endl не рахуємо.

У цьому випадку забагато констант цілих 8 буде.

Подякували: leofun011

305 Востаннє редагувалося ReAl (19.07.2018 21:32:52)

Re: Цікаві задачі

leofun01 написав:

Дозволено використовувати :
- бітові операції &, ^, |, &=, ^=, |=, &&, ||, ;
- операції зсуву <<, >>, <<=, >>=, >>>;
- присвоєння =, :=;
- порівняння ==, ===, !=, !==, >, <, >=, <=;
- стандартні бітові функції AND, XOR, OR, NOR, ... якщо такі надаються мовою програмування;
- цикли while, do while, for, until, але тільки 1 цикл і 1 раз;
- стрічки форматування виводу "%g", "{0}";
- стандартну функцію виводу 1 раз в коді (в циклі);
- константи і змінні, які займають до 8 біт включно;
- будь-яку мову програмування;

Все ж таки не втримався.
На базових бітових операціях робиться напівсуматор, а для інкрементора навіть повний суматор непотрібен, досить напівсуматорів по числу бітів. Для декрементора те ж саме, тільки десь інверсію треба вставити.
Щоб не сперечатися, жменя одиниць по коду це одна константа, чи жменя — просто завів змінну one :D
Все одно вийшло в сумі 4 сутності (дві змінних і дві константи, якщо не рахувати тих, що у коментарі ;) )
Друк довільної кількості чисел до 256 включно (від 255 до 0).
Для 15 можна викинути частину рядків, для 65535 додати :)

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

int main()
{
    uint8_t one = 1;
    uint8_t i = 15; // 0 для чисел від 255 до 0
    do {
        i ^= one
            | (~i & one) << one
            | (~i & (~i & one) << one) << one
            | (~i & (~i & (~i & one) << one) << one) << one
            | (~i & (~i & (~i & (~i & one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one) << one) << one
            ;
        printf("%d\n", i);
    } while (i);

    return i;
}

ліньки думати, як переписати красивіше, бо починав як для інкрементора, але тоді треба починати з
i = one - one;
і йти вгору, тоді константу «до якого числа» треба писати в умову циклу і щоб дійти до 255 потрібно брати змінні більшої за 8 розрядності, а це перевитрата бітів :-)

printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: leofun01, NagarD, /KIT\, Yola4

306

Re: Цікаві задачі

Yola написав:

Вкусіть мене за сраку. Мисліть ширше.

А щоб вас підняло та й гепнуло А ви точно програміст?

307 Востаннє редагувалося leofun01 (19.07.2018 23:45:11)

Re: Цікаві задачі

Ідея полягала в тому, щоб познайомити форумчан з магічними числами і їх застосуванням в програмуванні.

Розв'язки задачі :
для 0-7 :

#include <stdio.h>

int main(void) {
    unsigned char v = 184;
    do
        printf("%i\n", v & 7);
    while(v >>= 1);
    return 0;
}
Консоль написав:

0
4
6
7
3
5
2
1

для 0-15 :

#include <stdio.h>

int main(void) {
    unsigned short v2 = 42736;
    do
        printf("%i\n", v2 & 15);
    while(v2 >>= 1);
    return 0;
}
Консоль написав:

0
8
12
14
15
7
11
13
6
3
9
4
10
5
2
1

для 0-31 :

#include <stdio.h>

int main(void) {
    unsigned int v3 = 2359778272;
    do
        printf("%i\n", v3 & 31);
    while(v3 >>= 1);
    return 0;
}
Консоль написав:

0
16
24
28
30
31
15
23
27
13
22
11
21
26
29
14
7
19
9
20
10
5
18
25
12
6
3
17
8
4
2
1

інфо

Я знайшов ці числа самостійно, але виявилося, що існував мужичок, який теж страдав такою фігньою.
bin(10) == dec(2) == hex(2),
bin(1100) == dec(12) == hex(C),
bin(10111000) == dec(184) == hex(B8),
bin(1010011011110000) == dec(42736) == hex(A6F0),
bin(10001100101001110101101111100000) == dec(2359778272) == hex(8CA75BE0), ...
- існують і інші числа, які володіють подібними властивостями.
Джерела : Послідовності De Bruijn, Incubaid, Shift-register counter.
Також рекомендую заглянути на Графи De Bruijn.
Подякували: morgot, ReAl, Yola3

308

Re: Цікаві задачі

leofun01 написав:

Ідея полягала в тому, щоб познайомити форумчан з магічними числами і їх застосуванням в програмуванні.

Їх не треба застосовувати.

ukrainian.stackexchange.com - це питання-відповіді з української мови
Подякували: koala1

309

Re: Цікаві задачі

Yola написав:
leofun01 написав:

Ідея полягала в тому, щоб познайомити форумчан з магічними числами і їх застосуванням в програмуванні.

Їх не треба застосовувати.

Я не кажу, що їх треба застосовувати замість звичайних лічильників.
Але вони можуть бути дуже корисними для :

  • хешування;

  • шифрування;

  • обфускації;

  • генерування псевдо-випадкових чисел;

  • написання потенційно небезпечних програм.

В асемблері взагалі відкриваються величезні можливості для їх застосування.

310

Re: Цікаві задачі

leofun01 написав:
Yola написав:
leofun01 написав:

Ідея полягала в тому, щоб познайомити форумчан з магічними числами і їх застосуванням в програмуванні.

Їх не треба застосовувати.

Я не кажу, що їх треба застосовувати замість звичайних лічильників.
Але вони можуть бути дуже корисними для :

  • хешування;

  • шифрування;

  • обфускації;

  • генерування псевдо-випадкових чисел;

  • написання потенційно небезпечних програм.

В асемблері взагалі відкриваються величезні можливості для їх застосування.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

0x5f3759df або швидкий обернений квадратний корінь

[x|x<-[2..],all(>0)[x`mod`y|y<-[2..x-1]]]
Подякували: leofun011

311 Востаннє редагувалося ReAl (21.07.2018 13:25:53)

Re: Цікаві задачі

Не сперечайтеся. Є два поняття магічних чисел у програмуванні.
* Просто константа-літерал, або обрана майже довільно, або й загальновідома. Причому в інших місцях ця ж стала може використовуватися для іншого. Наприклад, десь 4 це число можливих з'єднань на IP, а поруч - число байтів у  32-бітному слові. "Магічність" тут у простій незрозумілості й безумовно шкідлива.
* Спеціально підібране число, яке прискорює чи спрощує якісь операції. Як приклад, окрім цієї задачі, можна навести множники, які разом зі зсувом замінюють ділення на константу для тих архітектур, де апаратного ділення нема чи воно повільне. Та навіть поліном crc у певному сенсі "магічний". Навіть якщо це число іменоване (і відкоментоване у місці визначення), скрізь у програмі використовується по імені, а не літералом, — воно залишається "магічним".

printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: leofun011