Алгоритм для строки или массива.

[iCaesy]

Задание:
Открыть файл, вынуть оттуда 2 цифры, присвоить переменной а первую цифру, переменной b вторую. // Это все понятно

Суть задачи: А - количество машин советской модели, B - количество иномарок. Нужно расставить машины в рад, так чтобы радом с иномаркой была хотя бы одна советская машина и наоборот.

Из этого я понял:
Возможные комбинации: (С - советская машина, И - иномарка)
Выставить по очереди (при условии что А=В) - С И С И С И С - подходит (самая легкая)

С И С И С С И С И - Подходит, то есть в середине можно поставить две одинаковых машины. (Это при А= В+1)

Если А=В+2 можно вот так

И С И И С И С И И С И

В общем нельзя две одинаковых в начале строки, и/или в конце, и три и больше подряд внутри строки.

Какой будет примерный алгоритм, и как лучше работать: Как с масивом или как со строкой ?
Pascal.

P.S Прошу не опошлять, так получилось с сокращениями

[SteAlzzer]

(при условии что А=В) - С И С И С И С

что-то тут не то)) У тебя 4 "С" и 3 "И". Но не как A=B)

Но все же.. на вскидку:
У тебя есть три случая
1. A=B
2. A>B
3. A<B

В первом все понятно, думаю. Просто последовательно переставляешь С и И и получаешь СИСИСИСИ

А для двух других случаев придумал кое-что. Не думаю, что это оптимально и быстро, но по идее должно работать)
В общем.. Создаешь массив на A+B. Записываешь в начало и конец С в случае A>B. Как ни крути, рядом с ними должны быть И, т.к. массив не замкнут (СС на конце или начале не принимаются). Дальше рядом с И ставишь по С. Дальше рассматриваешь массив, который еще не заполнен. И делаешь тоже самое. Пихаешь С по краям, к ним И, к И прицепляешь С.
Ну выглядит это приблизительно так
A = 8, B = 4;
1. _ _ _ _ _ _ _ _ _ _ _ _
2. С_ _ _ _ _ _ _ _ _ _С
3. СИ_ _ _ _ _ _ _ _ИС
4. СИС_ _ _ _ _ _СИС
5. Рассматриваем подмассив _ _ _ _ _ _ и возвращаемся к пунту 1.
Невооруженным глазом несложно заметить рекурсию)

В принципе, есть казусные ситуации. Например при А=5, Б=4. Но это вы уж сами рассмотрите, а то мне лень писать.

И кстати, вначале нужно сделать проверку на осуществимость задачи. Тоесть, Если, например А больше чем 2*Б, то ничего неполучится)

не силен в паскале. Но по идее, строка - это тот же массив. И я бы работал со строками, т.к. char меньше памяти занимает)))

[iCaesy]

Память роли не играет, главное реализовать задуманное Ща буду пробовать, если у кого есть идеи более короткого алгоритма, буду рад.

Если A - B > 6 или B - A > 6 -> Error !
Думаю такая проверка подойдет.

Есть прикрепленная тема, там все о массивах, вам туда.

[SteAlzzer]

Сообщение от iCaesy

Если A - B > 6 или B - A > 6 -> Error !
Думаю такая проверка подойдет.

не понял логики. Поясни, пожалуйста

[iCaesy]

При условии что нельзя в начале и конце ряда по 2 одинаковых авто, но можно между двумя ВВ разместить двк АА = ВААВ и так далее. Но если одних более чем шесть то уже не получается разместить таким способом.

[SteAlzzer]

Сообщение от iCaesy

При условии что нельзя в начале и конце ряда по 2 одинаковых авто, но можно между двумя ВВ разместить двк АА = ВААВ и так далее. Но если одних более чем шесть то уже не получается разместить таким способом.

это частный случай) Вот вам контрпример: возьмите, например, А = 7 и В = 3. Разница 5, что подходит к вашему условию. Но, однако, составить верную последовательность у вас не получится.

Условие все же заключается в том, что большее кол-во машин не должно привышать вдвое кол-во машин, которых меньше. Примитивная комбинаторика) Каждая наименьшая машина дает два вокантных места на соседство.

И, кстати, алгоритм по идее достаточно легок и быстр ( О(n), если не ошибаюсь)

[Serge_Bliznykov]

Сообщение от SteAlzzer

кстати, вначале нужно сделать проверку на осуществимость задачи. Тоесть, Если, например А больше чем 2*Б, то ничего неполучится)

+1
и, кстати, наоборот. Если B> 2*A - тоже не получится расставить машины.

а по поводу того, что брать - массив или строку - это уже сугубо личное дело. и массив можно сделать array[1..A+B] of byte или of char, и строка - по сути своей является массивом array[1..255] of char (правда, в случае строки ещё нулевой элемент задействован под длину строки)..
Если речь идёт о обычном DOS Pascal (TurboPascal), то надо учитывать, что в строке не может быть более 255 элементов.
Массив же ограничен только сегментом данных 64 кб.

Вся сложность в этой задачке именно в алгоритме перебора расстановок.

[SteAlzzer]

Сообщение от Serge_Bliznykov

+1
и, кстати, наоборот. Если B> 2*A - тоже не получится расставить машины.

а по поводу того, что брать - массив или строку - это уже сугубо личное дело. и массив можно сделать array[1..A+B] of byte или of char, и строка - по сути своей является массивом array[1..255] of char (правда, в случае строки ещё нулевой элемент задействован под длину строки)..
Если речь идёт о обычном DOS Pascal (TurboPascal), то надо учитывать, что в строке не может быть более 255 элементов.
Массив же ограничен только сегментом данных 64 кб.

Вся сложность в этой задачке именно в алгоритме перебора расстановок.

Да, я это дальше описал. Просто там как пример привел для одного случая. Спасибо.
Ну а алгоритм-то я в общем-то написал) Вы сами попробуйте на бумаге. Все работает)

[iCaesy]

Сообщение от SteAlzzer

Да, я это дальше описал. Просто там как пример привел для одного случая. Спасибо.
Ну а алгоритм-то я в общем-то написал) Вы сами попробуйте на бумаге. Все работает)

Ну у меня тоже есть кое какие мысли на счет алгоритма. Сейчас попробую реализовать через массив, 1..A+B , потом строку swap'ами.
Классно вам, написали уже ) Я 2й день голову ломаю.

[SteAlzzer]

Сообщение от iCaesy

Ну у меня тоже есть кое какие мысли на счет алгоритма. Сейчас попробую реализовать через массив, 1..A+B , потом строку swap'ами.
Классно вам, написали уже ) Я 2й день голову ломаю.

я имею ввиду попробуйте реализовать последовательность этого алгоритмя на бумаге. Возьмите 7 и 4, к примеру, и попробуйте)