301

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

Yola написав:

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

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

302 Востаннє редагувалося leofun01 (19.07.2018 22: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, Yola, 221VOLT4

303

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

leofun01 написав:

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

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

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

304

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

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

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

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

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

  • хешування;

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

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

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

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

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

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

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

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

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

306 Востаннє редагувалося dot (03.12.2019 11:46:53)

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

Хто не хоче відкивати яя шчодня до Різдва, а розвязувати вправи: https://adventofcode.com/

Дешчо припізнив — на два дня, але перші вправи досї можна розвязувати. Бачу, ньої вже тут колись давно згадували, тому просто нагадаю.

Подякували: 0x9111A, koala2

307

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

Долучуся і я.

Задача формулюється так:
Є дев'ять однозначних чисел від 1 до 9.
Achtung!! Нуля серед них немає.
Позначимо їх буквами r,e,s,p,u,b,l,i,k.
Сподіваюсь, що всі зрозуміли що r не обов'язково дорівнює 1,
а може мати будь яке значення.
Треба знайти всі варіанти, в яких числа зв'язані співвідношенням:
r * es = pub = l * ik
тобто всі числа задіяні по разу
Наприклад, 3 * 58 = 174 = 29 * 6
або 2 * 78 = 156 = 4 * 39

Подякували: 0xDADA11C7, leofun01, 221VOLT3

308

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

Python
>>> from itertools import permutations
>>> for r,e,s,p,u,b,l,i,k in permutations(range(1,10)):
    if r*(10*e+s)==100*p+10*u+b==l*(10*i+k):
        print(r,e,s,p,u,b,l,i,k)

        
2 7 8 1 5 6 4 3 9
3 5 8 1 7 4 6 2 9
4 3 9 1 5 6 2 7 8
6 2 9 1 7 4 3 5 8
Подякували: 0xDADA11C7, P.Y., plusxx, leofun01, 221VOLT5

309

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

koala написав:
Python
>>> from itertools import permutations
>>> for r,e,s,p,u,b,l,i,k in permutations(range(1,10)):
    if r*(10*e+s)==100*p+10*u+b==l*(10*i+k):
        print(r,e,s,p,u,b,l,i,k)

        
2 7 8 1 5 6 4 3 9
3 5 8 1 7 4 6 2 9
4 3 9 1 5 6 2 7 8
6 2 9 1 7 4 3 5 8

Тобто їх всього два варіанта??

Я чекав більшого...

310 Востаннє редагувалося leofun01 (20.03.2020 23:01:10)

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

elektryk написав:

Тобто їх всього два варіанта??

Я чекав більшого...

По перше: не 2, а 4.
По друге: вам дали готовий робочий код з результатом роботи цього коду. Якого "більшого" ви чекали ?

Подякували: 221VOLT, 0xDADA11C72

311

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

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

Тобто їх всього два варіанта??

Я чекав більшого...

По перше: не 2, а 4.
По друге: вам дали готовий робочий код з результатом роботи цього коду. Якого "більшого" ви чекали ?

Я вибачаюсь, за невдале висловлювання. Я думав, що результатів буде при наймі два десятки...

Що стосується не 2, а 4, то від перестановки монжників добуток не міняється...

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

312

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

«Готовий» — це якщо використовувати Python з його бібліотеками, де все є. Для якоїсь іншої мови, можливо, permutations доведеться реалізовувати власноруч (що, втім, не так вже й складно).

Подякували: leofun01, 221VOLT2

313

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

Наскільки я розумію, треба взяти всі можливі перестановки (а їх буде 9!)
і прогнати по умові.

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

314 Востаннє редагувалося 221VOLT (05.04.2020 22:55:53)

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

elektryk написав:

Долучуся і я.

Задача формулюється так:
Є дев'ять однозначних чисел від 1 до 9.
Achtung!! Нуля серед них немає.
Позначимо їх буквами r,e,s,p,u,b,l,i,k.
Сподіваюсь, що всі зрозуміли що r не обов'язково дорівнює 1,
а може мати будь яке значення.
Треба знайти всі варіанти, в яких числа зв'язані співвідношенням:
r * es = pub = l * ik
тобто всі числа задіяні по разу
Наприклад, 3 * 58 = 174 = 29 * 6
або 2 * 78 = 156 = 4 * 39

koala написав:
Python
>>> from itertools import permutations
>>> for r,e,s,p,u,b,l,i,k in permutations(range(1,10)):
    if r*(10*e+s)==100*p+10*u+b==l*(10*i+k):
        print(r,e,s,p,u,b,l,i,k)

        
2 7 8 1 5 6 4 3 9
3 5 8 1 7 4 6 2 9
4 3 9 1 5 6 2 7 8
6 2 9 1 7 4 3 5 8

якось так, коли строга статична типізація,
та ліньки запихати все в один рядочок :)

haskell
module Test where

p = [1..9] :: [Integer]

m d
  | k d       = False
  | otherwise = j d

k [] = False
k d
  | elem (head d) (tail d) == True = True
  | otherwise                      = k (tail d)

j d0 = y == x && y == z
  where
    [a,b,c,d,e,f,g,h,i] = d0
    x = (*) a $ read (show b ++ show c) :: Integer
    y = read (show d ++ show e ++ show f) :: Integer
    z = (*) g $ read (show h ++ show i) :: Integer

n :: [[Integer]] -> IO ()
n (x:xs) =
  if m x == True
  then do
    putStrLn $ show x
    n xs
  else do
    n xs

далі

~$ stack ghci
ghci> :l Test
ghci> import Data.List
ghci> n $ permutations p
[3,5,8,1,7,4,6,2,9]
[2,7,8,1,5,6,4,3,9]
[4,3,9,1,5,6,2,7,8]
[6,2,9,1,7,4,3,5,8]
*** Exception: Test.hs:(10,1)-(16,8): Non-exhaustive patterns in function n

замість Exception можна би було вивести "the end!",
написавши клаузу для матчингу пустого списку,
але ж лінь :)

Прихований текст

підгледіти код функції перестановок зі стандартної бібліотеки можна тут
https://hackage.haskell.org/package/bas … rmutations

-- | The 'permutations' function returns the list of all permutations of the argument.
--
-- >>> permutations "abc"
-- ["abc","bac","cba","bca","cab","acb"]
permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)
Подякували: leofun011

315 Востаннє редагувалося 221VOLT (03.05.2020 03:58:02)

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

haskell, перестановки, можливо комусь цікаво
(доповнення до попереднього повідомлення)

Прихований текст

GHCi> perms [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = r
  where
    p2 a [] = [[x]]
    p2 a b@(y:ys) = [(a:b)] ++ map (y:) (p2 a ys)
    r = concatMap (p2 x) (perms xs)




perms :: [a] -> [[a]]
perms [] = [[]]
perms [x] = [[x]]
perms (x:xs) = concatMap (insertElem x) (perms xs)
  where
    insertElem x [] = [[x]]
    insertElem x yss@(y:ys) = (x:yss) : map (y:) (insertElem x ys)



upd. по темі перестановок і комбінацій, ще таке писав-грався

Прихований текст
combs1 :: Int -> [a] -> [[a]]
combs1 0 _  = return []
combs1 n xs = do
  y:xs2 <- tails xs
  ys <- combs1 (n - 1) xs2
  return (y:ys)

{-
ghci> combs1 2 [0,1,2,3]
[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
ghci> combs1 3 [0,1,2,3]
[[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
ghci> combs1 4 [0,1,2,3]
[[0,1,2,3]]

ghci> combs1 3 [5,4..0]
[[5,4,3],[5,4,2],[5,4,1],[5,4,0],[5,3,2],[5,3,1],[5,3,0],[5,2,1],[5,2,0],[5,1,0],[4,3,2],[4,3,1],[4,3,0],[4,2,1],[4,2,0],[4,1,0],[3,2,1],[3,2,0],[3,1,0],[2,1,0]]
-}

+
я грався з генеруванням біткоін адрес, при роботі з безкінечними списками,
і дізнався, що є ще така функція, як replicateM

https://hackage.haskell.org/package/bas … replicateM

Прихований текст
replicateM :: Applicative m => Int -> m a -> m [a]

replicateM n act performs the action n times, gathering the results.

визначена ця функція в
https://hackage.haskell.org/package/bas … replicateM

Прихований текст
replicateM        :: (Applicative m) => Int -> m a -> m [a]
{-# INLINABLE replicateM #-}
{-# SPECIALISE replicateM :: Int -> IO a -> IO [a] #-}
{-# SPECIALISE replicateM :: Int -> Maybe a -> Maybe [a] #-}
replicateM cnt0 f =
    loop cnt0
  where
    loop cnt
        | cnt <= 0  = pure []
        | otherwise = liftA2 (:) f (loop (cnt - 1))

при цьому виявив, що в цієї коробочно-бібліотечної функції є недолік :)

Прихований текст

можливо, у новій версії GHC проблему виправили, не знаю -- тестив з рік назад, зі старішою версією компілятора

довелось мізкувати, як недолік цей виправити)
(гугл рулить)

Прихований текст
replicateM2 0 _ = return []
replicateM2 n xs = do
   b <- replicateM2 (n-1) xs
   a <- xs
   return (b ++ [a])

:)

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

316 Востаннє редагувалося koala (04.07.2021 20:16:00)

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

Знайти найменше ціле число, не менше за задане, яке можна розкласти на суму різних ступенів 3, наприклад 10=>10=32+30, 100=>108=34+33.

Python
def find_distinct_pow3(x):
    result = 0
    power = 1
    while x:
        x, digit = divmod(x, 3)
        if digit<2:
            result += power*digit
        else:
            result = 0
            x+=1
        power *= 3
    return result

Пояснення: перебираємо трійкове представлення числа. Якщо двійок немає - видаємо результат. Якщо зустріли двійку - додаємо 1 до розряду перед нею і викидаємо все до цього місця. В результаті маємо найменше число, що складається в трійковій системі з 0 та 1.

Подякували: leofun01, ch0r_t, P.Y., Chemist-i4

317 Востаннє редагувалося mamkin haker (24.01.2022 18:02:29)

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

задача №2 яка в 1 повідомленні

//згодиться?
#include <stdio.h>

int main()
{
    int v1 = 5;
    int v2 = 3;
    v1 += v2;
    v2 -= v1;
    v2 = -v2;
    v1 -= v2;
    printf("%i %i", v1, v2);
}

318 Востаннє редагувалося lucas-kane (15.12.2021 23:50:19)

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

Ось що значить вигадати велосипед заново ))

Прихований текст
mamkin haker написав:

задача №2 яка в 1 повідомленні

//згодиться?
#include <stdio.h>

int main()
{
    int v1 = 5;
    int v2 = 3;
    v1 += v2;
    v2 -= v1;
    v2 = -v2;
    v1 -= v2;
    printf("%i %i", v1, v2);
}

319 Востаннє редагувалося FakiNyan (14.04.2022 12:10:59)

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

Чи можна перевірити, чи дані у однозв'язному списку є паліндромом, при цьому шоб O(n) по часу, і O(1) по використаній пам'яті?
Я поки шо не бачу рішення без занесення даних зі списку в масив. По часу виходе O(n/2), бо нам треба перевірити, чи дані в масиві дзеркальні, а для цього треба зробити n/2 перевірок, але по пам'яті виходе O(n), бо створюємо додатковий масив для збереження даних.
осьо код

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let current = head;
    let arr = [];
  
    do {
      arr.push(current.val);
    } while (current = current.next);
  
    const mid = arr.length / 2;
    for (let i = arr.length - 1; i >= mid; i--) {
      if (arr[i] !== arr[arr.length - i - 1]) return false;
    }
    return true;
};

320

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

Ну, якщо витрати стеку не враховувати - то рекурсією саме воно і буде.
Інакше, боюся, О(1) не вийде.