Задача не практическая. Сам придумал и сам не могу решить.

На вход программе даётся размер и два массива чисел этого размера, один после другого. На вывод программа должна выдать элементы этих массивов в чередующемся порядке. Так вот, как сделать это без динамического выделения памяти? Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

Здравствуйте, Дон Рэба, Вы писали:

ДР>Задача не практическая. Сам придумал и сам не могу решить.

ДР>На вход программе даётся размер и два массива чисел этого размера, один после другого. На вывод программа должна выдать элементы этих массивов в чередующемся порядке. Так вот, как сделать это без динамического выделения памяти? Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

Похоже, подразумевается, что на вход поступает поток чисел? Тогда — никак, и это легко доказать: вывод ты теоретически не можешь начать до тех пор, пока не доберешься до первого элемента второго массива. Следовательно, тебе каким-то образом придется запомнить все элементы первого, что без (дополнительной) памяти невозможно.

Про рекурсию забыли?

T>Про рекурсию забыли?
А рекурсия что ли не использует дополнительную память?

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

A>Похоже, подразумевается, что на вход поступает поток чисел? Тогда — никак, и это легко доказать: вывод ты теоретически не можешь начать до тех пор, пока не доберешься до первого элемента второго массива. Следовательно, тебе каким-то образом придется запомнить все элементы первого, что без (дополнительной) памяти невозможно.

Дополнительной памяти можно использовать сколько угодно. Нельзя только выделять её динамичиски. То есть, нет new, нет списков или функций с переменным числом параметров. Я как раз запнулся на том, что возможно поместить эти массивы на стэк с помощью рекурсии, но не понятно как затем изменить их порядок или почему это невозможно.

Здравствуйте, Дон Рэба, Вы писали:

ДР>возможно поместить эти массивы на стэк с помощью рекурсии, но не понятно как затем изменить их порядок

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

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

MBo>вставить первый массив в один стек, потом перебросить во второй — вот элементы и встанут в нужном порядке
MBo>Получится аналог очереди.

Э... Второго нет. Имеется в виду стэк локальных переменных.

Здравствуйте, Дон Рэба, Вы писали:

A>>Похоже, подразумевается, что на вход поступает поток чисел? Тогда — никак, и это легко доказать: вывод ты теоретически не можешь начать до тех пор, пока не доберешься до первого элемента второго массива. Следовательно, тебе каким-то образом придется запомнить все элементы первого, что без (дополнительной) памяти невозможно.

ДР>Дополнительной памяти можно использовать сколько угодно. Нельзя только выделять её динамичиски. То есть, нет new, нет списков или функций с переменным числом параметров. Я как раз запнулся на том, что возможно поместить эти массивы на стэк с помощью рекурсии, но не понятно как затем изменить их порядок или почему это невозможно.

А если сделать просто:

#include <stdio.h>

void inout(int size)
{
        int i;
        int a[size], v;

        for (i = 0; i < size; ++i)
                scanf("%d", &a[i]);
        for (i = 0; i < size; ++i) {
                scanf("%d", &v);
                printf("%d %d\n", a[i], v);
        }
}

int main()
{
        int i, n;

        scanf("%d", &n);
        inout(n);
}

(Кажется, стандарт C99 позволяет определять в функциях массивы заранее неизвестного размера.)
Компилирую с помощью gcc.
Затем даю на вход последовательность: 3 1 2 3 4 5 6
На выходе получаю:
1 4
2 5
3 6

Задача чисто вымышленная. Как я описал в первом сообщении, даны только функции с целочисленными переменными, а также read и write. Только глубина рекурсии не ограничена.

Здравствуйте, Дон Рэба, Вы писали:

ДР>Задача чисто вымышленная. Как я описал в первом сообщении, даны только функции с целочисленными переменными, а также read и write. Только глубина рекурсии не ограничена.

Т.е. (локальных) массивов нет?

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

AVC>Здравствуйте, Дон Рэба, Вы писали:

AVC>Т.е. (локальных) массивов нет?

Мне только динамическое выделение памяти хотелось исклюлчить. Наличие или отсутствие фисксированного размера локальных массивов не влияет на выразительность, поэтому можно использовать их и итерацию. А вот alloca и тому подобное, это уже жульничество.

Мне кажется, эта задача нерешаема, но я пока не понимаю как это доказать. Думаю о приведении к ругулярным выражениям — там есть похожие задачи с доказательствами.

Здравствуйте, Дон Рэба, Вы писали:

ДР>Здравствуйте, AVC, Вы писали:

AVC>>Здравствуйте, Дон Рэба, Вы писали:

AVC>>Т.е. (локальных) массивов нет?

ДР>Мне только динамическое выделение памяти хотелось исклюлчить. Наличие или отсутствие фисксированного размера локальных массивов не влияет на выразительность, поэтому можно использовать их и итерацию. А вот alloca и тому подобное, это уже жульничество.

ДР>Мне кажется, эта задача нерешаема, но я пока не понимаю как это доказать. Думаю о приведении к ругулярным выражениям — там есть похожие задачи с доказательствами.

ИМХО, задача сводится к инвертированию половины входной последовательности.
Так что, возможно, решение есть.
Если применить маленький "хак" (в Си можно указывать не только на динамическую память), то получается такой вариант:

#include <stdio.h>

int n = 0;

struct list {
        int          v;
        struct list *next;
};

void bar(struct list *p)
{
        int v;
        if (p != NULL) {
                bar(p->next);
                scanf("%d", &v);
                printf("%d %d\n", p->v, v);
        }
}

int foo(int k, struct list *p)
{
        struct list r;

        r.next = p;
        scanf(" %d", &r.v);
        if (++k < n)
                foo(k, &r);
        else
                bar(&r);
}

int main()
{
        scanf(" %d", &n);
        foo(0, NULL);
        return 0;
}

Здесь нет никакого динамического выделения памяти, только рекурсия.
Если указатели тоже использовать нельзя, то надо много думать.
Вопрос в том, удастся ли инвертировать последовательность.

Здравствуйте, Дон Рэба, Вы писали:

ДР>Задача не практическая. Сам придумал и сам не могу решить.

ДР>На вход программе даётся размер и два массива чисел этого размера, один после другого. На вывод программа должна выдать элементы этих массивов в чередующемся порядке. Так вот, как сделать это без динамического выделения памяти? Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

На изменяемых списках это можно сделать так:

struct list_item
{
    list_item const* next;
    int data;
};

void run(int n, list_item const* const &head, list_item const* &tail);

void start(int n)
{
    list_item const* head = NULL;
    run(n,head,head);
}

void run(int n, list_item const* const &head, list_item const* &tail)
{
    if(n != 0)
    {
        // наращиваем список, читая первый массив
        list_item item = { NULL, read(); };
        tail = &item;
        run(n-1, head, item.next);
    }
    else
    {
        // читаем второй массив и тут же выводим его, перемежая с первым
        list_item const* here = head;
        while(here != NULL)
        {
            write(here->data); here = here->next;
            write(read());
        }
    }
}

На неизменяемых... тоже можно, но заморочнее.

На неизменяемых:

struct Cons
{
    int const data;
    Cons const* const next;
    
    Cons(int d, Cons const* n) : data(d), next(n) {}
};

void start(int count) { read_first(NULL, count); }

void read_first(Cons const* list, int todo)
{
    if(todo)
        read_first(&Cons(read(),list), todo-1);
    else
        invert_first(list, NULL);
}

void invert_first(Cons const* srclist, Cons const* dstlist)
{
    if(srclist)
        invert_first(srclist->next, &Cons(srclist->data,dstlist));
    else
        read_second_and_write(dstlist);
}

void read_second_and_write(Cons const* list)
{
    while(list) // уж позволим себе заменить концевую рекурсию на итерации
    {
        write(list->data);
        write(read());
        list = list->next;
    }
}

Здравствуйте, Дон Рэба, Вы писали:

ДР>Задача не практическая. Сам придумал и сам не могу решить.

ДР>На вход программе даётся размер и два массива чисел этого размера, один после другого. На вывод программа должна выдать элементы этих массивов в чередующемся порядке. Так вот, как сделать это без динамического выделения памяти? Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

джавист?

Здравствуйте, Дон Рэба, Вы писали:

ДР>Дополнительной памяти можно использовать сколько угодно. Нельзя только выделять её динамичиски. То есть, нет new, нет списков или функций с переменным числом параметров. Я как раз запнулся на том, что возможно поместить эти массивы на стэк с помощью рекурсии, но не понятно как затем изменить их порядок или почему это невозможно.

Упс, уже всё придумали до меня
А я тоже придумал список в стеке рожать

А ещё можно нарожать по нитке для каждого числа и хитро-хитро застваить их друг друга ждать и отпускать
Тоже нестандартный изврат получится

Здравствуйте, Дон Рэба, Вы писали:

ДР>Задача не практическая. Сам придумал и сам не могу решить.

ДР>На вход программе даётся размер и два массива чисел этого размера, один после другого. На вывод программа должна выдать элементы этих массивов в чередующемся порядке. Так вот, как сделать это без динамического выделения памяти? Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

решение на основе связанного списка: записываем оба массива в один односвязный список, "перематываем" список на половину, чтобы получить хвост первого массива, и выводим:

#include <iostream>

struct list_item
{
    list_item* prev_;
    int x_;
};

// rewinds specified list item to n positions backward
void rewind(list_item*& i, int n)
{
    while(n-- != 0)
        i = i->prev_;
}

// prints list item
void print(const list_item* i)
{
    std::cout << i->x_ << " ";
}

// prints list using alternate order
void print(const list_item* first, const list_item* second)
{
    if (first != 0)
    {
        // at first print the previous items
        print(first->prev_, second->prev_);
        // then print the current items
        print(first);       print(second);
    };
}

// builds list of inputed values
void input_rec(unsigned int size, unsigned int current_index, list_item* prev)
{
    if (current_index == size)
    {
        list_item* first_tail = prev, *second_tail = prev;
        // receive the tail of the first list
        rewind(first_tail, size / 2);
        // print both lists
        print(first_tail, second_tail);
        return;
    }

    list_item i = {prev, 0};
    std::cin >> i.x_;

    input_rec(size, ++current_index, &i);
}

int main()
{
    // size of single array
    unsigned int size;
    std::cin >> size;

    // size for both arrays
    size *= 2;

    input_rec(size, 0, 0);
    return 0;
}

Здравствуйте, Дон Рэба.

ДР>... Всё что есть это функции с целочисленными переменными на стэке, а также read и write.

Предлагаю эффективное C++ решение без указателей легко(через define) переводимое в чистый C и даже(ручками) в BASIC. Оно работает быстрее всех приведённых ранее и использует меньше памяти если память занимаемая элементом последовательности меньше или равна размеру фрейма стека вызова функции. Оно достаточно легко масштабируется на большие размеры стека. Увы в BASIC должно быть написано слишком много кода.

typedef int number;//Для типов с маленьким sizeof решение особенно эффективно.

number cnt0 = 0;
void read (number&x) { x=++cnt0; }
void write(number x) { printf("%d ",x);}

//Если размер стека может достигать 4Gb то
//на Си\Бейсике это около 45 функций с фибоначиевыми именами
//execute2 execute3 execute5 execute8 execute13 execute21...
//Внутри каждой из них выделяется локальный массив
//размером равным числу в имени функции.
template < unsigned int array_size >
void execute ( unsigned int N )
{
    number data[array_size];
    for (int i=0; i!=N; ++i)
        read(data[i]);
    for (int i=0; i!=N; ++i)
    {
        write(data[i]);
        read (data[0]);
        write(data[0]);
    }
}

//Если размер стека может достигать 4Gb то
//на Си\Бейсике это около 45 функций с фибоначиевыми именами
//manager2 manager3 manager5 manager8 manager13 manager21...
template < unsigned int limit >
void stack_manager ( unsigned int N )
{
    enum { next_limit = limit<200000000?(limit+limit/2):1 };
    if (limit<N)
        ::template stack_manager < next_limit > ( N );
    else
        ::template execute < limit > (N);
}

void solution ( unsigned int N )
{
//Типичная длина одной последовательности 20 - 200 элементов
    ::template stack_manager < 60 > ( N );
}

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

А почему именно фибоначчи (степень 1.6), а не степень 2? Борьба с перерасходом стека?

Кстати, у тебя степень <1.5, поскольку limit+limit/2 <= limit*1.5

твой ряд           2 3 4 6 9  13  19    28  42   ...
округление вверх   2 3  5 8 12  18    27  41
фибоначчи          2 3  5 8   13    21        44 ...

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

К>А почему именно фибоначчи (степень 1.6), а не степень 2? Борьба с перерасходом стека?
Конечно. Хотя списки в стеке лучше если сразу несколько элементов выделять.


К>Кстати, у тебя степень <1.5, поскольку limit+limit/2 <= limit*1.5
К>

К>твой ряд           2 3 4 6 9  13  19    28  42   ...
К>округление вверх   2 3  5 8 12  18    27  41
К>фибоначчи          2 3  5 8   13    21        44 ...
К>

Ну это я для примера. Принцип продемонстрировать. Можно и правильные числа поставить.