Дистанционная подготовка: помогите с решением
помогите с решением
от Dima Svetov - Понедельник 10 Февраль 2014, 23:14
1414. Фишки
  не могу придумать рекурентное соотношение для этой задачи

пытался так:
чтобы поставить фишку в место N нужно удалить все фишки до N-2 включительно и собственно поставить N
то есть структура какая-то такая
void ins(int N){
del(N-2)
std::cout << N
}
для удаления нужно сначала вставить N-1 элемент потом удалить все до него потом удалить N и этот элемент.В общем получается какая-то ахинея не могу понять куда думать. Все остальные задачи на рекурсию вроде более менее понятны интуитивно, но эта кошмар.

Помогите хотя бы с рассуждениями тк раньше подобное не решал.
Re: помогите с решением
от Dima Svetov - Вторник 11 Февраль 2014, 16:56
  помогите пожалуйста)
Re: помогите с решением
от Dima Svetov - Четверг 13 Февраль 2014, 16:27
  ответьте кто-нибудь
Re: помогите с решением
от Иван Трофимов - Четверг 13 Февраль 2014, 17:44
  Будем расставлять фишки с конца(то есть сначала поставим фишку N, потом N - 1 и т.д.)
Итак, как мы ставим фишку на место K?
Изначально весь массив пустой
1.Сначала мы должны поставить фишку на позицию K - 1, при этом поставить только ее(нельзя допустить, чтобы в результате работы функции какие-то еще фишки были поставлены).
2.Теперь ставим фишку на позицию K.
3.Удалим фишку с позиции K - 1.

void ins(int n)
{
    if(n == 1)
    {
        cout << 1 << " ";
        return;
    }
    ins(n - 1);
    cout << n << " ";
    del(n - 1);
}

почти аналагично удаляем элемент с позиции i:
1.Ставим на i - 1
2.Удаляем с i
3.Удаляем с i - 1

void del(int n)
{
    if(n == 1)
    {
        cout << -1 << " ";
        return;
    }
    ins(n - 1);
    cout << -n << " ";
    del(n - 1);
}

Не забудь объявить шаблоны фунцкий ins и del, т.к. они вызываются перекрестно.

void solve(int n)
{
    for(int i = n; i >= 1; --i)
        ins(i);
}
Re: помогите с решением
от Dima Svetov - Четверг 13 Февраль 2014, 19:51
  пасибо))
Re: помогите с решением
от Никита Пушкин - Суббота 16 Август 2014, 21:22
  К сожалению, такая программа работать не будет. В конце вывода будет куча лишних чисел, хотя начало правильное.
Re: помогите с решением
от Никита Пушкин - Суббота 16 Август 2014, 21:28
  Например, как будет выглядеть ответ для значения "2" , если использовать Ваш алгоритм? Сначала ставим фишку в 1 клетку, затем во вторую, а потом зачем-то удаляем фишку из первой клетки и снова ее туда ставим. Для более крупных чисел все будет еще хуже.
В общем, без массива, в котором хранится состояние поля, никак не обойтись.