201 Відповідь від Yola Востаннє редагувалося Yola (14.11.2015 15:04:25)

  • Yola
  • Yola
  • Replace Group
  • Поза форумом
  • Звідки: ukrainian.stackexchange.com
  • Дата реєстрації: 16.04.2013
  • Повідомлень: 1 088
    • Репутація: 587

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

quez написав:

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

Тоді я не розумію ваше запитання, чому у вас на першому місці в деяких парах ідуть молодші? Має бути так ХсХм ХсДм ДсХм.

Якщо ви все ж таки хочете додати пари з молодшими на першому місці, то робіть це з усіма парами, ви просто подвоїте кількість але коефіцієнт буде тим самим 2/3.

Yola вебсайт

202 Відповідь від quez

  • quez
  • quez
  • Replace Team
  • Поза форумом
  • Звідки: Новий Єрусалим
  • Дата реєстрації: 01.05.2014
  • Повідомлень: 3 103
    • Репутація: 1621

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

Я не дуже чітко виразився. На першому місці хлопчик, якого вибрали.

Задачу з теорії ймовірностей треба формулювати так, щоб множина елементарних подій була очевидною. В моїй інтерпретації "обираємо хлопчика", у вас — "обираємо пару, в якій є хлопчик". Залежно від формулювання, відповідь буде 1/2 або 2/3.

203 Відповідь від Replace

  • Replace
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 06.04.2012
  • Повідомлень: 2 895
    • Репутація: 2105

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

$families = [];
$size = 100000;
for ($i = 1; $i <= $size; $i++) {
    $families[] = [rand(0, 1), rand(0, 1)];
}

$familiesBoy = [];
foreach ($families as $children) {
    if (in_array(1, $children)) {
        $familiesBoy[] = $children; 
    }
}

$total = 0;
$girls = 0;

foreach ($familiesBoy as $children) {
    if (in_array(0, $children)) {
        $girls++; 
    }
    $total++;
}

echo $girls / $total;

~ 0.67

Replace вебсайт

204 Відповідь від 0x9111A

  • 0x9111A
  • 0x9111A
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 10.03.2014
  • Повідомлень: 627
    • Репутація: 548

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

От є у нас масив.
Імплементувати get\set\set_all що працють з O(1).

205 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 313
    • Репутація: 13060

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

Вибачте, можна культурніше умову дати? "У нас є масив" - це означає, що вже задана стандартна для певної мови структура даних - масив чи ви хотіли сказати "розробити структуру зберігання однорідних даних, що підтримує операції звертання по індексу"? Які саме вхідні параметри для цих get/set/set_all мають бути, і який функціонал у них передбачений? За загальною логікою, масив.set повинен приймати параметром інший аналогічний масив, чи мається на увазі заміна одного елемента? А set_all тоді що має робити? Якщо set_all встановлює значення всіх елементів, то як має працювати set_all(lambda)? Чи не має працювати?

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

koala вебсайт

206 Відповідь від 0x9111A

  • 0x9111A
  • 0x9111A
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 10.03.2014
  • Повідомлень: 627
    • Репутація: 548

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

Структуру даних можете взяти довільну, але треба отакий інтерфейс, не більше й не менше.

int get(size_t i);
void set(size_t i, int v);
void set_all(int v);

207 Відповідь від Yola

  • Yola
  • Yola
  • Replace Group
  • Поза форумом
  • Звідки: ukrainian.stackexchange.com
  • Дата реєстрації: 16.04.2013
  • Повідомлень: 1 088
    • Репутація: 587

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

Це типу якесь додаткове поле використовувати для set_all, і в кожному полі мати мітку часу, що змінювати на кожному сеті, а під час гету брати або елемент, або з поля set_all в залежності де новіша мітка дати?

Подякували: Arete, FakiNyan, koala, 0x9111A4

Yola вебсайт

208 Відповідь від Arete

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 419

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

Для зчитування чи записування елементу в якусь структуру даних за константний час ця структура даних повинна підтримувати  random access ітератор. Наприклад, для масивів С/С++ це зводиться до арифметики вказівників, а починаючи з 11 стандарту є ще і std::array, що підтримує загальні правила роботи з контейнерами даних в STL.

209 Відповідь від Arete

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 419

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

0x9111A написав:

Структуру даних можете взяти довільну, але треба отакий інтерфейс, не більше й не менше.

int get(size_t i);
void set(size_t i, int v);
void set_all(int v);

Get і set для масиву і так буде О(1), а от як set_all зробити меншим за O(n) поки що незрозуміло.

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

210 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • На форумі
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 13 832
    • Репутація: 5579

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

Arete написав:
0x9111A написав:

Структуру даних можете взяти довільну, але треба отакий інтерфейс, не більше й не менше.

int get(size_t i);
void set(size_t i, int v);
void set_all(int v);

Get і set для масиву і так буде О(1), а от як set_all зробити меншим за O(n) поки що незрозуміло.

все дуже просто. Перед усім цим дійством в пам'яті треба створити безліч масивів, кожен з котрих буде містити купу однакових цифрочисел, котрі унікальні для кожного з масивів, а потім просто передавати вказівник на початок масиву, у котрого всі числа == v  8)

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

211 Відповідь від Arete

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 419

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

FakiNyan написав:
Arete написав:
0x9111A написав:

Структуру даних можете взяти довільну, але треба отакий інтерфейс, не більше й не менше.

int get(size_t i);
void set(size_t i, int v);
void set_all(int v);

Get і set для масиву і так буде О(1), а от як set_all зробити меншим за O(n) поки що незрозуміло.

все дуже просто. Перед усім цим дійством в пам'яті треба створити безліч масивів, кожен з котрих буде містити купу однакових цифрочисел, котрі унікальні для кожного з масивів, а потім просто передавати вказівник на початок масиву, у котрого всі числа == v  8)

геніально  :D

212 Відповідь від Yola

  • Yola
  • Yola
  • Replace Group
  • Поза форумом
  • Звідки: ukrainian.stackexchange.com
  • Дата реєстрації: 16.04.2013
  • Повідомлень: 1 088
    • Репутація: 587

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

Arete написав:

Get і set для масиву і так буде О(1), а от як set_all зробити меншим за O(n) поки що незрозуміло.

Тому що ви думаєте про масив лише як про набір елементів, а можливо вам треба цю структуру доповнити чимось. Перед вашим повідомленням я навів варіант розв'язання проблеми. Уважніше.

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

Yola вебсайт

213 Відповідь від 0x9111A Востаннє редагувалося 0x9111A (15.12.2015 11:19:34)

  • 0x9111A
  • 0x9111A
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 10.03.2014
  • Повідомлень: 627
    • Репутація: 548

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

Yola написав:

Це типу якесь додаткове поле використовувати для set_all, і в кожному полі мати мітку часу, що змінювати на кожному сеті, а під час гету брати або елемент, або з поля set_all в залежності де новіша мітка дати?

Вірно, як варіант. Але є ще варіант (хоча суть схожа і там і там)

214 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 728
    • Репутація: 2466

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

Це питання не алгоритму, а конкретної мови програмування. Бо на кількох відомих мені, вирішується елементарно просто присвоєнням нового масису в змінну.

Vo_Vik вебсайт

215 Відповідь від quez

  • quez
  • quez
  • Replace Team
  • Поза форумом
  • Звідки: Новий Єрусалим
  • Дата реєстрації: 01.05.2014
  • Повідомлень: 3 103
    • Репутація: 1621

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

Vo_Vik написав:

Це питання не алгоритму, а конкретної мови програмування. Бо на кількох відомих мені, вирішується елементарно просто присвоєнням нового масису в змінну.

Ви не зробите новий масив за O(1), якщо я вас правильно зрозумів.

216 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 728
    • Репутація: 2466

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

quez написав:
Vo_Vik написав:

Це питання не алгоритму, а конкретної мови програмування. Бо на кількох відомих мені, вирішується елементарно просто присвоєнням нового масису в змінну.

Ви не зробите новий масив за O(1), якщо я вас правильно зрозумів.

Гм.

<?php $this->value = $new_value; ?>

?

Vo_Vik вебсайт

217 Відповідь від VTrim

  • VTrim
  • VTrim
  • =)
  • Поза форумом
  • Дата реєстрації: 07.09.2014
  • Повідомлень: 3 314
    • Репутація: 2296

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

Vo_Vik написав:
quez написав:
Vo_Vik написав:

Це питання не алгоритму, а конкретної мови програмування. Бо на кількох відомих мені, вирішується елементарно просто присвоєнням нового масису в змінну.

Ви не зробите новий масив за O(1), якщо я вас правильно зрозумів.

Гм.

<?php $this->value = $new_value; ?>

?

Допустимо ви додали 5 масивів до масиву за час N.  Чи додасте в той масив ще 10000 масивів за той самий час?

218 Відповідь від Arete Востаннє редагувалося Arete (17.12.2015 22:09:09)

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 419

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

Vo_Vik написав:
quez написав:
Vo_Vik написав:

Це питання не алгоритму, а конкретної мови програмування. Бо на кількох відомих мені, вирішується елементарно просто присвоєнням нового масису в змінну.

Ви не зробите новий масив за O(1), якщо я вас правильно зрозумів.

Гм.

<?php $this->value = $new_value; ?>

?

Ви говорили про мови програмування, а самі даєте приклад на php (жартую). А що там під капотом відбувається можете в двох словах описати?

219 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 728
    • Репутація: 2466

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

Arete написав:

Ви говорили про мови програмування, а самі даєте приклад на php (жартую). А що там під капотом відбувається можете в двох словах описати?

Я ж кажу, що це питання конретної мови програмування. Що вони там роблять хз. Може виділяють нову память під новий масив і прикріпляють вказівник змінної до нової області в пам’яті. Мене не цікавить.

Vo_Vik вебсайт

220 Відповідь від 0x9111A

  • 0x9111A
  • 0x9111A
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 10.03.2014
  • Повідомлень: 627
    • Репутація: 548

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

Ну от і як тут не пожартувати про php-шників  :D