LINUX.ORG.RU
← Поиск в БД не зная таблицы
Задачка по гео-поиску →
Ответ на: комментарий от Trieforce

Тело цикла - твоё рекурсивное действие.
Вместо рекурсивного вызова функции ты делаешь push. Вместо получения параметра внутри рекурсивного вызова ты делаешь pop.

Xellos ★★★★★
()
Ответ на: комментарий от Trieforce 
while(n>1){
  p.push(n-1);
  --n;
}

Вот это вот просто запихивает в стэк значения n..2.

Ведь не того хотелось-то?

sergv ★
()
Ответ на: комментарий от Trieforce 
#include <iostream>

using namespace std;

void foo(int n) {
        if (n == 0) {
                return;
        }
        foo(n-1);
        cout << n << "\n";
        foo(n-1);
}

int main()
{
        //............< arg, what to do after call >
        vector < pair < int, int> > s1;

        s1.push_back(make_pair(4, 0));
        foo(4); cout << "\n";
        while (!s1.empty()) {
                int n,m;
                pair<int,int> p;
                p = s1.back(); s1.pop_back();
                n = p.first; m = p.second;
                if (m) {
                        cout << m << "\n";
                }
                if (n == 0) continue;
                s1.push_back(make_pair(n - 1, n));
                s1.push_back(make_pair(n - 1, 0));
        }
}
Reset ★★★★★
()
Ответ на: комментарий от Trieforce

Ещё раз повторяю. Напиши рекурсивный алгоритм. Обычным образом, с рекурсивными вызовами.
Затем делай раз - вызов рекурсивной функции замени на push, делай два - получение параметров в функции замени на pop, делай три - оберни всё в while (!stack.is_empty()){}.

Xellos ★★★★★
()

Да, и в development. Пошёл тикет писать.

Xellos ★★★★★
() 
#include <stack>
#include <iostream>

void foo(int n) {
    std::stack<int> s;
    s.push(n);
    while(!s.empty()) {
        n = s.top();
        s.pop();
        if (n > 0) {
            s.push(n-1);
            std::cout << n << std::endl;
            s.push(n-1);
        }
    }
}
anonymous
()
Ответ на: комментарий от Reset

Мой способ, кстати, тоже не совсем корректный, хотя и дает одинаковый вывод.

Reset ★★★★★
()
Ответ на: комментарий от Reset

А если так? 

#include <stack>
#include <iostream>
void foo(int n) {
    std::stack< std::pair<int,int> > s1;
    std::stack< std::pair<int,int> > s2;
    std::pair<int,int> num;
    s1.push(std::make_pair(n,0));

    for(int k=1;k!=0;) {
        k=0;
        while(!s1.empty()) {
            num = s1.top();
            s1.pop();
            if(num.second==0) {
                if (num.first > 0) {
                    s2.push(std::make_pair(num.first-1,0));
                    s2.push(std::make_pair(num.first, num.second+1));
                    s2.push(std::make_pair(num.first-1,0));
                }
                k++;
            } else if(num.first!=num.second) {
                s2.push(std::make_pair(num.first, num.second+1));
                k++;
            } else {
                s2.push(std::make_pair(num.first, num.second));
            }
        }
        while(!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }
    while(!s1.empty()) {
        num = s1.top();
        std::cout << num.first << std::endl;
        s1.pop();
    }
}

anonymous
()

А задача именно так формулируется, иди это просто пример? Потому что для такой задачи можно обойтись обычным циклом с каким нить хитрым преобразованием индекса.

AIv ★★★★★
()
Ответ на: комментарий от anonymous

Похоже на то, что в общем случае действительно надо делать два стека (не зря в своем варианте я сделал s1), но у тебя очень сложный код и for(int k=1;k!=0;) { намекает на то, что у тебя оно работает только для конкретной этой задачи, а в общем случае работать не будет.

Reset ★★★★★
()
Ответ на: комментарий от Reset

Это ведь можно проверить, но k там просто «битовый флаг». А если сделать так, то памяти меньше потребуется: 

void foo(int n) {
    int max,k;
    std::pair<int,int> num;
    std::list< std::pair<int,int> > L1,L2;
    L2.push_back(std::make_pair(n,0));
    while(!L2.empty()) {
        max = n;
        L1.splice(L1.begin(),L2);
        L2.clear();
        for(k=0;!L1.empty()&&k<5;k++) {
            num = L1.front(); L1.pop_front();
            if(num.second==0) {
                if(num.first>0) {
                    L2.push_back(std::make_pair(num.first-1,0));
                    L2.push_back(std::make_pair(num.first, 1));
                    L2.push_back(std::make_pair(num.first-1,0));
                }
            } else if(num.first!=num.second) {
                num.second++;
                L2.push_back(num);
            } else {
                if(num.first<=max) {
                    cout << num.first << std::endl;
                    max = num.first-1;
                } else {
                    L2.push_back(num);
                }
            }
        }
    }
}

anonymous
()
Ответ на: комментарий от Trieforce

если рекурсия происходит в центре подсчетов, то тогда создай 

//recursive
void foo(a1,a2,a3)
{
    localvars;
    work1;
    if(do_part2)foo(b1,b2,b3);
    work2;
    if(do_part3)foo(c1,c2,c3);
    work3;
}
//stack
struct foo {
    localvars;
    int part;
    
    foo(a1,a2,a3,...):part(0){...}
    void operator (vector<foo>& S){
      switch(part){
      case 0:part1(S);break;
      case 1:part2(S);break;
      case 2:part3(S);break;
      case 3:S.pop_back();break;
      default:abort();
      }
    }
    void part1(vector<foo>& S){
         ++part;

         work1;
         if(do_part2){S.emplace(b1,b2,b3);return;}
         part2(S);
    }
    void part2(vector<foo>& S){
         ++part;

         work2;
         if(do_part3){S.emplace(a1,a2,a3);return;}
         part3(S);
    }
    ...
};

ckotinko ☆☆☆
()
Ответ на: комментарий от ckotinko

или даже выход можно сделать через default:S.pop_back(); а не абортиться

и part сделать enum {} или enum class {} чтоб точно не просрать полимеры

ckotinko ☆☆☆
()

Это обострение чтоли, писать на сях с рекурсиями и прочими лиспами? Автор, что конкретно-то ты хочешь получить?

rand ★
()
Ответ на: комментарий от anonymous

Все проще: 

void foo(int n) {
    std::pair<int,int> num;
    std::stack< std::pair<int,int> > S;
    S.push(std::make_pair(n,0));
    while(!S.empty()) {
        num = S.top(); S.pop();
        if(num.second==0) {
            if(num.first>0) {
                S.push(std::make_pair(num.first-1,0));
                S.push(std::make_pair(num.first,  1));
                S.push(std::make_pair(num.first-1,0));
            }
        } else {
            cout << num.first << std::endl;
        }
    }
}

anonymous
()

А еще любой код всегда можно порубить в FSM: 

#include <iostream>
#include <stack>

void foor(int n) 
{
	if (n > 0) 
	{			
		foor(n-1);
		std::cout << n << " ";
		foor(n-1);
	}
}

void fooi(int n)
{
	enum { BEGIN, FIRST, MIDDLE, LAST, END };

	std::stack<std::pair<int, int> > stack;

	int loc = BEGIN;	

	while ( !stack.empty() || loc != END )
	{
		switch ( loc ) 
		{
		case BEGIN:
			if (n > 0) 
				loc = FIRST;
			else
				loc = END;
			break;

		case FIRST:
			stack.push(std::make_pair<int,int>(MIDDLE, n));
			n = n-1;
			loc = BEGIN;
			break;

		case MIDDLE:
			std::cout << n << " ";
			loc = LAST;
			break;

		case LAST:
			stack.push(std::make_pair<int,int>(END, n));
			n = n-1;
			loc = BEGIN;
			break;

		case END:
			if ( !stack.empty() )
			{
				std::pair<int, int> v = stack.top();
				stack.pop();
				loc = v.first;
				n = v.second;
			}
			break;
		}
	}
}

int main()
{
	foor(5);
	std::cout << "\n";
	fooi(5);
}
qrck ★★
() 
void foo(int n) {
    int i=0,j,k = 1;
    while(k!=n+1) {
        std::cout << k << std::endl;
        for(j=++i,k=1;j&2!=0;k++)
            j>>=1;
    }
}
anonymous
()
Ответ на: комментарий от qrck

P.S. А еще если в голове нарисовать версию этого кода на каком-нибудь ФП, то на ум приходит такая вот итеративная «развертка»:

void foo(int n) 
{
	std::list<int> res;
	std::list<int>::iterator iter;

	for (int i=1; i<=n; i++)
	{
		res.push_back(i);
		iter = res.end();
		std::copy(res.begin(), --iter, std::back_inserter(res));
	}

	for (iter = res.begin(); iter != res.end(); iter++)
		std::cout << *iter << " ";
}

Топикстартер, - выбирай, коммунити тебе накидало кучу решений ;)

qrck ★★
()
Ответ на: комментарий от Xellos

Так работает же! 

#include<stack>
#include<queue>
#include<iostream>
using namespace std;
stack<int> r;
queue<int> p;
void print(int n) {
    stack<int> p;
    p.push(n);
    while(not p.empty()){
        while(n>1){
            p.push(n-1);
            --n;
        }
        cout << ' ' << p.top();
        n=p.top();
        p.pop();
        while(n>1){
            p.push(n-1);
            --n;
        }
    }
}

Trieforce ★
() автор топика
Ответ на: комментарий от Trieforce

Ну тогда все просто. Запускаем цикл до (1<<n)-1. Берем индекс в битовом представлении, приписываем слева единичку, считаем число единичек слева направо до первого нуля - число единичек и будет число для вывода.

AIv ★★★★★
()
Ответ на: комментарий от Reset

Два стека конечно хорошо... но так вот попроще будет:-) 

#include <stdio.h>
#include <stdlib.h>

int main( int argc, const char** argv ){
	if(argc!=2){ printf("usage: ./recsym n\n"); return 1; }
	int n = atoi(argv[1]);
	for( int i=0; i<(1<<n)-1; i++ ){
		int k = 0; 
		while( k<32 && i&(1<<k) ) k++;
		printf("%i\n", k+1 );
	}
	return 0;
}

AIv ★★★★★
()
Ответ на: комментарий от Trieforce

Что работает-то? У тебя какой-то вырожденный пример, который можно решить 100500 вариантами с рекурсией и таким же количеством вариантов без рекурсии.

Xellos ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Поиск в БД не зная таблицы
Development
Задачка по гео-поиску →