Помогите, пожалуйста, с задачкой

← →
ProgRAMmer Dimonych © (2007-02-21 18:47) [0]

Чё-то торможу. Задача, похоже, на списки (те самые, которые бывают одно- и двунаправленные).

Задан зашифрованный текст и целые числа M и K. Текст был зашифрован следующим образом:
1) Считаем, что исходный текст замкнут, т.е. за последней буквой следует первая;
2) K-ая буква текста выписывается в отдельную строку и вычёркивается из текста, далее выписывается и вычёркивается следующая K-а буква и так до тех пор, пока не будут вычеркнуты все буквы текста.
3) M присваивается значение, равное номеру позиции, которую занимала в исходном тексте последняя вычеркнутая буква.
Например, при K=3 текст "структуры данных" будет зашифрован как "ртыаытудхкнун ср", M=8. Расшифровать текст, зная, что последняя вычеркнутая буква в исходном тексте на M-ом месте. Пусть K=4, M=5, расшифруйте текст "асолпжуехев ю".

Чувствую, что решение будет не очень сложным, но чего-то как-то не могу выйти на него: зарешался, наверное.

Заранее спс.

← →
oldman © (2007-02-21 18:52) [1]

> Например, при K=3 текст "структуры данных" будет зашифрован
> как "ртыаытудхкнун ср", M=8.

Отсюда и танцую.
Решение не только не сложное, а простейшее.
Код писать лень.

← →
ProgRAMmer Dimonych © (2007-02-21 18:55) [2]

> oldman © (21.02.07 18:52) [1]
У меня пока самое лучшее, что придумал, - это смоделировать шифрование, используя вместо букв их номера в исходном тексте, а потом на основе этого восстанавливать, т.к. длина зашифрованного текста равна длине исходного текста... Это сюда?

← →
Ketmar © (2007-02-21 18:58) [3]

спать ложись.

← →
Alx2 © (2007-02-21 18:59) [4]

Простая задачка.
Достаточно идти в обратном направлении. На M-ю позицию ставим последнюю букву шифровки. На M-k -ую перпоследнюю..

← →
oldman © (2007-02-21 19:00) [5]

Ответ:
"желаю успехов"

← →
ProgRAMmer Dimonych © (2007-02-21 19:01) [6]

> Ketmar © (21.02.07 18:58) [3]
Так ведь рано ещё?

> Alx2 © (21.02.07 18:59) [4]
Проблема в том, что текст замкнут, т.е. при втором, третьем и т.д. проходах некоторые буквы пропускаются. Например, в приведённом примере предпоследняя в зашифрованнос тексте буква "с" находится на 1 позиции, а не на 8-3=5-ой.

← →
ProgRAMmer Dimonych © (2007-02-21 19:02) [7]

> oldman © (21.02.07 19:00) [5]
Т.е. нормально?

Может быть, есть другие подходы, более простые и интересные? Скажите "нет" - и я пойду писать программу и ложиться спать ;).

← →
oldman © (2007-02-21 19:07) [8]

> Alx2 © (21.02.07 18:59) [4]
> Простая задачка.
> Достаточно идти в обратном направлении. На M-ю позицию ставим
> последнюю букву шифровки. На M-k -ую перпоследнюю..

Можно и наоборот.
В тсходной фразе - 13 букв. зная, что К=4 (М ваще на фиг не нужно) получаем шаги для фразы "асолпжуехев ю"
1. .............
2. ...а.........
3. ...а...с.....
4. ...а...с...о.
5. ..ла...с...о.
6. ..ла...сп..о.
7. ж.ла...сп..о.
8. ж.ла..усп..о.
9. жела..усп..о.
10. жела..усп.хо.
11. жела..успехо.
12. жела..успехов
13. жела. успехов
14. желаю успехов

Вот и все...

← →
ProgRAMmer Dimonych © (2007-02-21 19:11) [9]

> oldman © (21.02.07 19:07) [8]
Действительно. Спасибо огромное за вторую идею решения. Буду пробовать оба варианта - вреда не принесёт, заодно потренируюсь. Получается, что при любом раскладе одно из чисел M или K - лишнее. Так вроде?

← →
oldman © (2007-02-21 19:15) [10]

> Alx2 © (21.02.07 18:59) [4]
> Простая задачка.
> Достаточно идти в обратном направлении. На M-ю позицию ставим
> последнюю букву шифровки. На M-k -ую перпоследнюю..

При последних оставшихся N буквах (N<K) твоя система не работает...
То есть, первые (блин, последние) К-1 букв ты правильно не расставишь...

← →
oldman © (2007-02-21 19:18) [11]

То есть при первом шаге мы имеем:

....ю........

А второго шага нет :(
Поскольку "пробел" должен стоять сразу после "ю"...

ProgRAMmer Dimonych, используй мой вариант.
Я твою задачу решил ты сам видишь за сколько минут...

← →
Alx2 © (2007-02-21 19:39) [12]

>oldman © (21.02.07 19:18)

Здесь 13 - простое число. Может злую шутку сыграть.
К примеру, из 12 букв = 4*3 букв
"желаю успех"
получаем
"асж хулеюп"

Говоря про "наоборот" я подразумевал также растущую (ранее убывавшую) длину.

← →
Alx2 © (2007-02-21 19:40) [13]

Сорри. Последний пост не считать. Ошибся.

← →
Alx2 © (2007-02-21 19:44) [14]

Вот поправка к 12 посту: будет "асж хулеюеп"
Остальное в силе.

← →
oldman © (2007-02-21 19:48) [15]

> Alx2 © (21.02.07 19:44) [14]

Мне по барабану, что будет.
расшивровке по моему алгоритму поддается?
А по твоему - нет!

>oldman © (21.02.07 19:18)
То есть хотел сказать, что при K=4 и "асж хулеюеп" будут неточности.
Здесь все хорошо при взаимно простых длинне и k. Иначе строка будет разбиваться на фрагменты, внутри которых твой способ будет работать. Но не на всех вместе.
Просто пуская алгоритм "задом наперед", получается примитивное и рабочее решение.

> ProgRAMmer Dimonych © (21.02.07 19:11) [9]
>Получается, что при любом раскладе одно из чисел M или K - лишнее

М, как и К, - не лишнее. имхо, оно для проверки, верно ли расшифровано.

> Давай расшифруем "асж хулеюеп"

Модераторов на вас не напасешься.

Удалено модератором

Я, действительно, жутко торможу. Вместо двенадцати букв воткнул 11 и почти матом. Все равно не работает способ oldman в том виде, как он привел в в oldman © (21.02.07 19:07)

>oldman

Приношу свои извинения. Тормозеж у меня был жесточайший :(

Помогите, пожалуйста, с задачкой Найти похожие ветки