Здравствуйте, nikov, Вы писали:

N>...Надо посчитать количество комнат в доме за минимальное количество проходов через двери.
Дык, ответ-то будет?
Например, это

Автор: Erop
Дата: 18.06.08

ответ?

Здравствуйте, nikov, Вы писали:

using System;
using System.Console;
using Nemerle.Utility;
using Nemerle.Imperative;

class Rooms
{
    public this(n : int)
    {
        rooms_ = array(n);
        def rnd = Random(DateTime.Now.Millisecond);
        rooms_.Generate(_ => rnd.Next() % 100 >= 50);
    }
    public Test() : bool
    {
        rooms_[pos_];
    }
    public Set(f : bool) : void
    {
        rooms_[pos_] = f;
    }
    public Next(n : int) : void
    {
        pos_ += n;
        steps_ += n;
        while (pos_ >= rooms_.Length)
            pos_ -= rooms_.Length;
    }
    public Prev(n : int) : void
    {
        pos_ -= n;
        steps_ += n;
        while (pos_ < 0)
            pos_ += rooms_.Length;
    }
    private rooms_ : array[bool];
    private mutable pos_ : int = 0;
    [Accessor]
    private mutable steps_ : int = 0;
}

module Program
{
    Main() : void
    {
        try
        {
            def test(n)
            {
                def rooms = Rooms(n);
                def loop(steps)
                {
                    def half = steps / 2;
                    def checkForvard(steps)
                    {
                    | 0 => 0
                    | _ =>
                        if (!rooms.Test())
                        {
                            steps
                        }
                        else
                        {
                            rooms.Next(1);
                            checkForvard(steps - 1)
                        }
                    }

                    def forvard(steps)
                    {
                    | 1 => rooms.Set(true);
                    | _ =>
                        rooms.Set(true);
                        rooms.Next(1);
                        forvard(steps - 1);
                    }

                    def checkBackward(steps)
                    {
                    | 0 => 0
                    | _ =>
                        if (rooms.Test())
                        {
                            steps
                        }
                        else
                        {
                            rooms.Prev(1);
                            checkBackward(steps - 1)
                        }
                    }

                    def backward(steps)
                    {
                    | 1 => rooms.Set(false);
                    | _ =>
                        rooms.Set(false);
                        rooms.Prev(1);
                        backward(steps - 1);
                    }

                    def f = checkForvard(half);
                    when (f != 0)
                        return (steps - f, f, steps, 'f');
                    forvard(steps - half);
                    rooms.Prev(steps);

                    def b = checkBackward(half);
                    when (b != 0)
                        return (steps + half - b, b, steps, 'b');
                    backward(steps - half);
                    rooms.Next(steps);

                    loop(steps * 2);
                }
                def res = loop(1);
                (n, res, rooms.Steps);
            }
            
            $[1..100].Iter(n => WriteLine($"$(test(n).ToString())"));
        }
        catch
        {
        | ex is Exception => WriteLine(ex)
        }
        _ = ReadKey();
    }
}

module Util
{
    public static Generate[T](this arr : array[T], fn : int -> T) : void
    {
        for (mutable i = 0; i < arr.Length; ++i)
            arr[i] = fn(i);
    }
}

(1, (1, 1, 2, f), 2)
(2, (2, 1, 2, b), 5)
(3, (3, 1, 4, f), 9)
(4, (4, 2, 4, b), 15)
(5, (5, 1, 4, b), 16)
(6, (6, 2, 8, f), 24)
(7, (7, 1, 8, f), 25)
(8, (8, 4, 8, b), 37)
(9, (9, 3, 8, b), 38)
(10, (10, 2, 8, b), 39)
(11, (11, 1, 8, b), 40)
(12, (12, 4, 16, f), 56)
(13, (13, 3, 16, f), 57)
(14, (14, 2, 16, f), 58)
(15, (15, 1, 16, f), 59)
(16, (16, 8, 16, b), 83)
(17, (17, 7, 16, b), 84)
(18, (18, 6, 16, b), 85)
(19, (19, 5, 16, b), 86)
(20, (20, 4, 16, b), 87)
(21, (21, 3, 16, b), 88)
(22, (22, 2, 16, b), 89)
(23, (23, 1, 16, b), 90)
(24, (24, 8, 32, f), 122)
(25, (25, 7, 32, f), 123)
(26, (26, 6, 32, f), 124)
(27, (27, 5, 32, f), 125)
(28, (28, 4, 32, f), 126)
(29, (29, 3, 32, f), 127)
(30, (30, 2, 32, f), 128)
(31, (31, 1, 32, f), 129)
(32, (32, 16, 32, b), 177)
(33, (33, 15, 32, b), 178)
(34, (34, 14, 32, b), 179)
(35, (35, 13, 32, b), 180)
(36, (36, 12, 32, b), 181)
(37, (37, 11, 32, b), 182)
(38, (38, 10, 32, b), 183)
(39, (39, 9, 32, b), 184)
(40, (40, 8, 32, b), 185)
(41, (41, 7, 32, b), 186)
(42, (42, 6, 32, b), 187)
(43, (43, 5, 32, b), 188)
(44, (44, 4, 32, b), 189)
(45, (45, 3, 32, b), 190)
(46, (46, 2, 32, b), 191)
(47, (47, 1, 32, b), 192)
(48, (48, 16, 64, f), 256)
(49, (49, 15, 64, f), 257)
(50, (50, 14, 64, f), 258)
(51, (51, 13, 64, f), 259)
(52, (52, 12, 64, f), 260)
(53, (53, 11, 64, f), 261)
(54, (54, 10, 64, f), 262)
(55, (55, 9, 64, f), 263)
(56, (56, 8, 64, f), 264)
(57, (57, 7, 64, f), 265)
(58, (58, 6, 64, f), 266)
(59, (59, 5, 64, f), 267)
(60, (60, 4, 64, f), 268)
(61, (61, 3, 64, f), 269)
(62, (62, 2, 64, f), 270)
(63, (63, 1, 64, f), 271)
(64, (64, 32, 64, b), 367)
(65, (65, 31, 64, b), 368)
(66, (66, 30, 64, b), 369)
(67, (67, 29, 64, b), 370)
(68, (68, 28, 64, b), 371)
(69, (69, 27, 64, b), 372)
(70, (70, 26, 64, b), 373)
(71, (71, 25, 64, b), 374)
(72, (72, 24, 64, b), 375)
(73, (73, 23, 64, b), 376)
(74, (74, 22, 64, b), 377)
(75, (75, 21, 64, b), 378)
(76, (76, 20, 64, b), 379)
(77, (77, 19, 64, b), 380)
(78, (78, 18, 64, b), 381)
(79, (79, 17, 64, b), 382)
(80, (80, 16, 64, b), 383)
(81, (81, 15, 64, b), 384)
(82, (82, 14, 64, b), 385)
(83, (83, 13, 64, b), 386)
(84, (84, 12, 64, b), 387)
(85, (85, 11, 64, b), 388)
(86, (86, 10, 64, b), 389)
(87, (87, 9, 64, b), 390)
(88, (88, 8, 64, b), 391)
(89, (89, 7, 64, b), 392)
(90, (90, 6, 64, b), 393)
(91, (91, 5, 64, b), 394)
(92, (92, 4, 64, b), 395)
(93, (93, 3, 64, b), 396)
(94, (94, 2, 64, b), 397)
(95, (95, 1, 64, b), 398)
(96, (96, 32, 128, f), 526)
(97, (97, 31, 128, f), 527)
(98, (98, 30, 128, f), 528)
(99, (99, 29, 128, f), 529)
(100, (100, 28, 128, f), 530)

Здравствуйте, WolfHound, Вы писали:

Минус за отсутствие описания алгоритма. Что за мода на форуме пошла?
Интересно общение в группе разработчиков тоже через исходники осуществляется?

Здравствуйте, Erop, Вы писали:

E>Ну, например, включаем свет в комнате 1, потом идём во виторую, третью, четвёртую... и везде свет гасим.
E>Пусть мы последний раз встретили горящую лампочку в комнате номер К, и потом ещё К комнат не встречали. Тогда идём назад, в 1-ю и смотрим, горит ли там свет. Если горит, то возращаемся назад в 2*К и идём дальше, если нет, то всего есть К-1 комнат...
Мой алгоритм в общем случае лучше.
Ибо для твоего можно подобрать волшебную комбинацию когда он сделает больше шагов чем мой.
А мой не зависит от того в каком положении находятся выключатели.

Здравствуйте, vb-develop, Вы писали:

VD>Минус за отсутствие описания алгоритма. Что за мода на форуме пошла?
VD>Интересно общение в группе разработчиков тоже через исходники осуществляется?
Исходный код это ацки формализованный алгоритм.
Если ты не можешь прочиать простой код то как ты вобще работаешь?

Здравствуйте, Erop, Вы писали:

E>Ну, например, включаем свет в комнате 1, потом идём во виторую, третью, четвёртую... и везде свет гасим.
E>Пусть мы последний раз встретили горящую лампочку в комнате номер К, и потом ещё К комнат не встречали. Тогда идём назад, в 1-ю и смотрим, горит ли там свет. Если горит, то возращаемся назад в 2*К и идём дальше, если нет, то всего есть К-1 комнат...
Если я тебя правильно понял то вот твой алгоритм вместе с генерацией одной из ацких комбинаций.
В данном случае он всегда хуже моего.

            def test2(n)
            {
                def rooms = Rooms(n);
                mutable j = 4;
                for (mutable i = 0; i < n; ++i)
                {
                    if (i == j)
                    {
                        rooms.Set(true);
                        j = j * j;
                    }
                    else
                    {
                        rooms.Set(false);
                    }
                    rooms.Next(1);
                }
                def loop(cur, last)
                {
                    def last = if (rooms.Test()) cur else last;
                    rooms.Set(false);
                    if (last * 2 == cur)
                    {
                        rooms.Prev(cur - 1);
                        if (rooms.Test())
                        {
                            find(1);
                        }
                        else
                        {
                            (last - 1, cur)
                        }
                    }
                    else
                    {
                        rooms.Next(1);
                        loop(cur + 1, last);
                    }
                }
                and find(cur)
                {
                    def cur = cur + 1;
                    rooms.Next(1);
                    if (rooms.Test())
                    {
                        rooms.Set(false);
                        loop(cur, cur);
                    }
                    else
                    {
                        find(cur);
                    }
                }
                rooms.Set(true);
                def res = find(1);
                (if (res[0] == n) 't' else 'f', n, res, rooms.Steps);
            }

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, vb-develop, Вы писали:

VD>>Минус за отсутствие описания алгоритма. Что за мода на форуме пошла?
VD>>Интересно общение в группе разработчиков тоже через исходники осуществляется?
WH>Исходный код это ацки формализованный алгоритм.
WH>Если ты не можешь прочиать простой код то как ты вобще работаешь?

Я, например, не понял, что обозначают строчки лога. Скажем такая: (9, (9, 3, 8, b), 38)
Кроме того, там, где я работаю, принято писать комментарии...
Кстати, мне показалось, или твой алгоритм сразу же знает число комнат в доме?
В любом случае, интересно бы понять сколько дверей надо открыть для дома в N комнат, в худжем случае?

Здравствуйте, vb-develop, Вы писали:

VD>Включим свет в той комнате, где мы находились (если он был выключен). Начинаем идти по кругу до тех пор пока не встретим комнату с включенным светом. Такая комната существует, т.к мы из неё вышли и нигде свет не выключали. Когда находим такую комнату выключаем свет, идем обратно в ту комнату, в которой мы включили свет. Разумеется эту комнату определяем по числу переходов между комнатами. Если в этой комната комнате свет окажется выключен, значит количество переходов между комнатами без единицы и есть количество комнат в доме. В противном случае повторяем итерацию до тех пор пока свет в исходной комнате не окажется выключен.
Можно проще. Начинаем ходить вправо-влево добавляя каждый раз на одну комнату к каждому направлению. Слева в каждой новой посещенной компате свет выключаем, справа — включаем. Как только приходим в комнату, в которой до этого свет включали/выключали, а он там выключен/включен — считаем длину последнего перемещения направо/налево. Сложность ~n^2.

Здравствуйте, nikov, Вы писали:

N>В здании есть N комнат. В каждой комнате есть две двери. Из комнаты номер 1 есть двери в комнаты 2 и N. Из комнаты номер N есть двери в комнаты (N-1) и 1. И любой другой комнаты с номером M есть двери в комнаты (M-1) и (M+1). То есть, комнаты расположены по кругу. Все комнаты одинаковы, и их номера на них не написаны. В каждой комнате есть выключатель, который включает/гасит свет в этой комнате. Из комнаты нельзя увидеть, горит ли свет в соседних команатах, если не зайти туда. В начале выключатели во всех комнатах находятся в произвольном положении, а вы находитесь в одной из комнат. В доме есть привидение, которое стирает любые отметки (например, надписи на стенах), но оно не может включать/гасить свет. Надо посчитать количество комнат в доме за минимальное количество проходов через двери.

1. Проходим в произвольно выбранном направлении X комнат, начиная с текущей. В первой попытке X = 2. 
2. В каждой посещенной комнате изменяем состояние лампочки на противоположное и запоминаем(записываем) новое состояние лампочки.
3. Возвращаемся в исходную комнату и получаем количество лампочек Y, состояния которых не совпадают с записанными 
   (эти лампочки, если они есть, будут расположены подряд, поэтому не обязательно их считать, достаточно засечь порядковый номер последней).
4. Если Y == 0, то X <= N. В этом случае увеличиваем X в два раза (строго) и повторяем действия сначала.
5. Если Y != 0, то находим количество комнат по формуле: N = X - Y.

Принципиально, что X нужно увеличивать именно в 2 раза. Если увеличивать X больше, то могут возникнуть троекратные посещения одной комнаты при движении в одном направлении, что приведет к ошибке. Если меньше, чем в два, то не будет удовлетворено требование минимального количества проходов.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, vb-develop, Вы писали:

VD>>Минус за отсутствие описания алгоритма. Что за мода на форуме пошла?
VD>>Интересно общение в группе разработчиков тоже через исходники осуществляется?
WH>Исходный код это ацки формализованный алгоритм.
WH>Если ты не можешь прочиать простой код то как ты вобще работаешь?
Извини, но то как я работаю к теме топика это не имеет ни малейшего отношения. И если что, то алгоритмы интересны не только программистам.

Здравствуйте, vb-develop, Вы писали:

VD>>>Минус за отсутствие описания алгоритма. Что за мода на форуме пошла?
VD>>>Интересно общение в группе разработчиков тоже через исходники осуществляется?
WH>>Исходный код это ацки формализованный алгоритм.
WH>>Если ты не можешь прочиать простой код то как ты вобще работаешь?
VD>Извини, но то как я работаю к теме топика это не имеет ни малейшего отношения. И если что, то алгоритмы интересны не только программистам.
После того как ты написал выделеное имеет.

Здравствуйте, Erop, Вы писали:

E>Я, например, не понял, что обозначают строчки лога. Скажем такая: (9, (9, 3, 8, b), 38)
А ты на что-то кроме них смотрел?

E>Кроме того, там, где я работаю, принято писать комментарии...
А что мне за это платят?
Тем более что если туда понаписать комментариев ничего нового не добавится.

E>Кстати, мне показалось, или твой алгоритм сразу же знает число комнат в доме?
Показалось.

E>В любом случае, интересно бы понять сколько дверей надо открыть для дома в N комнат, в худжем случае?
Последняя колонка лога.

Здравствуйте, WolfHound, Вы писали:

WH>А что мне за это платят?
WH>Тем более что если туда понаписать комментариев ничего нового не добавится.
Да ты можешь и вообще решений не предлагать, в принципе

E>>Кстати, мне показалось, или твой алгоритм сразу же знает число комнат в доме?
WH>Показалось.
Ну там не совсем понятно где уже алгоритм, а где ещё генерилка

E>>В любом случае, интересно бы понять сколько дверей надо открыть для дома в N комнат, в худжем случае?
WH>Последняя колонка лога.

Ну типа для 9 комнат 38 дверей? Тогда это довольно плохой результат...

Здравствуйте, WolfHound, Вы писали:

WH>После того как ты написал выделеное имеет.
Мощно ты запрогался, однако
Даже алгоритм по-русски объяснить не можешь...
Да и хамить наверное лучше бы разучиться

Здравствуйте, Erop, Вы писали:

E>Мощно ты запрогался, однако
E>Даже алгоритм по-русски объяснить не можешь...
А ты?
Мне пришлось не мало додумать чтобы реализовать твой алгоритм.
Ибо банальное переписывание твоего описания приводит к зацикливанию.

E>Да и хамить наверное лучше бы разучиться
Re[2]: Количество комнат

Автор: vb-develop
Дата: 18.06.08

Здравствуйте, Erop, Вы писали:

E>Ну типа для 9 комнат 38 дверей? Тогда это довольно плохой результат...
Сравни со своим.
колличество комнат, мой результат, твой результат(там еще над комбинацией поколдовать можно... еще хуже будет)

1 2 7
2 5 12
3 9 17
4 15 22
5 16 27
6 24 32
7 25 37
8 37 42
9 38 47
10 39 70
11 40 75
12 56 80
13 57 85
14 58 90
15 59 95
16 83 100
17 84 105
18 85 110
19 86 115
20 87 120
21 88 125
22 89 130
23 90 135
24 122 140
25 123 145
26 124 150
27 125 155
28 126 160
29 127 165
30 128 170
31 129 175
32 177 180
33 178 185
34 179 256
35 180 261
36 181 266
37 182 271
38 183 276
39 184 281
40 185 286
41 186 291
42 187 296
43 188 301
44 189 306
45 190 311
46 191 316
47 192 321
48 256 326
49 257 331
50 258 336
51 259 341
52 260 346
53 261 351
54 262 356
55 263 361
56 264 366
57 265 371
58 266 376
59 267 381
60 268 386
61 269 391
62 270 396
63 271 401
64 367 406
65 368 411
66 369 416
67 370 421
68 371 426
69 372 431
70 373 436
71 374 441
72 375 446
73 376 451
74 377 456
75 378 461
76 379 466
77 380 471
78 381 476
79 382 481
80 383 486
81 384 491
82 385 496
83 386 501
84 387 506
85 388 511
86 389 516
87 390 521
88 391 526
89 392 531
90 393 536
91 394 541
92 395 546
93 396 551
94 397 556
95 398 561
96 526 566
97 527 571
98 528 576
99 529 581
100 530 586

VD>>Включим свет в той комнате, где мы находились (если он был выключен). Начинаем идти по кругу до тех пор пока не встретим комнату с включенным светом. Такая комната существует, т.к мы из неё вышли и нигде свет не выключали. Когда находим такую комнату выключаем свет, идем обратно в ту комнату, в которой мы включили свет. Разумеется эту комнату определяем по числу переходов между комнатами. Если в этой комната комнате свет окажется выключен, значит количество переходов между комнатами без единицы и есть количество комнат в доме. В противном случае повторяем итерацию до тех пор пока свет в исходной комнате не окажется выключен.
U>Можно проще. Начинаем ходить вправо-влево добавляя каждый раз на одну комнату к каждому направлению. Слева в каждой новой посещенной компате свет выключаем, справа — включаем. Как только приходим в комнату, в которой до этого свет включали/выключали, а он там выключен/включен — считаем длину последнего перемещения направо/налево. Сложность ~n^2.

Модификация:
ходим вправо-влево, но добавляем к направлению не одну комнату, а удваиваем "длину направления". Т.е. доходим до комнат: +1, -2, +4, -8, ... Соответственно, длина каждого прохода будет в 1,5 раза больше: 1, 3, 6, 12, ...
Сложность, вроде бы ~2n.
Возможно, выбирая коэффициент увеличения "длины направления", можно ещё улучшить результат. Думать лень, но на ум приходит число e как наиболее эффективное основание системы счисления.

Кстати, эта задачка напоминает проблему выделение памяти для растущего списка, когда будущий размер его даже примерно неизвестен.

Здравствуйте, nikov, Вы писали:

N>В здании есть N комнат. В каждой комнате есть две двери. Из комнаты номер 1 есть двери в комнаты 2 и N. Из комнаты номер N есть двери в комнаты (N-1) и 1. И любой другой комнаты с номером M есть двери в комнаты (M-1) и (M+1). То есть, комнаты расположены по кругу. Все комнаты одинаковы, и их номера на них не написаны. В каждой комнате есть выключатель, который включает/гасит свет в этой комнате. Из комнаты нельзя увидеть, горит ли свет в соседних команатах, если не зайти туда. В начале выключатели во всех комнатах находятся в произвольном положении, а вы находитесь в одной из комнат. В доме есть привидение, которое стирает любые отметки (например, надписи на стенах), но оно не может включать/гасить свет. Надо посчитать количество комнат в доме за минимальное количество проходов через двери.

Идем вперед и запоминаем состояние лампочек. Каждые 2*n комнат проверяем, не повторяется ли состояние дважды: [1..n] и [n..2*n]. Если повторяется, меняем состояние в последней комнате и возвращаемся на n комнат назад. Если состояние в n-й комнате изменилось, число комнат равно n. Если нет, продолжаем в том же духе. Для 2 комнат худший случай -- 7 переходов, для 3 комнат -- 10, для 4 -- 17.

Здравствуйте, WolfHound, Вы писали:

WH>колличество комнат, мой результат, твой результат(там еще над комбинацией поколдовать можно... еще хуже будет)
WH>

WH>1 2 7
WH>2 5 12
WH>

Что-то тут не так
1) По моему алгоритму при одной комнате в здании делаем так:
1.1) зажигаем свет в 1-й комнате
1.2) гасим во второй (1 дверь)
1.3) видим в третьей темноту (2-я дверь)
1.4) возвращаемся во вторую комнату (3-я дверь)
1.5) возвращаемся в первую комнату (4-я дверь) и видим что свет погас

Если предположить, что в комнате две комнаты, то мой алгоритм находит ответ за 8 дверей (что во второй не важно, если был свет, гасим, в третьей свет снова будет, потом пойдём ещё в четвёртую и в пятую и повернём назад)

Это что касается моего алгоритма.

Теперь давай посмотрим на твой. Какие двери и в каком порядке мы открываем, чтобы за две двери убедиться, что в здании только одна комната? Видимо идём во вторую комнату и возвращаемся в первую? А как тогда мы ещё за три двери убедимся, что комнат всего 2?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, WolfHound, Вы писали:

WH>>колличество комнат, мой результат, твой результат(там еще над комбинацией поколдовать можно... еще хуже будет)
WH>>

WH>>1 2 7
WH>>2 5 12
WH>>

E>Теперь давай посмотрим на твой. Какие двери и в каком порядке мы открываем, чтобы за две двери убедиться, что в здании только одна комната? Видимо идём во вторую комнату и возвращаемся в первую? А как тогда мы ещё за три двери убедимся, что комнат всего 2?

Пойдем назад, изменим состояние лампочки, перейдем на две комнаты вперед, убедимся, что состояние изменилось и сделаем соответствующие выводы.
Получается такой алгоритм. Включаем свет в текущей комнате (=Left), идем вперед до ближайшей включенной (=Right), выключаем, возвращаемся (в Left). Если состояние не изменилось, идем назад до ближайшей выключенной (=Left), включаем, возвращаемся (в Right). Если ее состояние не изменилось... и так далее.
Число шагов в худшем случае равно N*(N+1)/2 + 1. Я подозреваю, что это наилучший результат из возможных. Но у уважаемого WolfHound'а результат лучше. Nemerle не владею, поэтому сказать, в чем тут дело, не могу.