如何使用堆栈计算n的阶乘

Question

我需要使用堆栈计算n的阶乘，而我所做的代码不会返回任何结果。我也不知道pop的确是什么（它的第二个参数是什么）所以我只是在那里使用了一个随机值。我使用int **x;，因为我不知道该放什么pop(&mystack,*x);。

#include <iostream>
using namespace std;
int n;
int aux;
int aux1;
int aux2;
int **x;
typedef struct {
    int content[100];
    int top;
} stack;
stack mystack;

int push(stack *somestack,int somevalue)
{
    if (somestack->top+1>=100)
        return 1;
    (*somestack).top++;
    (*somestack).content[(*somestack).top]=somevalue;
    return 0;
}

int pop(stack *somestack, int *oldvalue)
{
    if((*somestack).top==0)
    {
        return 1;
    }
    *oldvalue=(*somestack).content[(*somestack).top];
    return 0;
}

int main()
{
    cout<<"n=";
    cin>>n;
    push(&mystack,n);
    int direction=1;
    while(mystack.top>=1)
    {
        if((direction==1)&&(mystack.content[mystack.top]>1))
        {
            aux=mystack.content[mystack.top];
            push(&mystack,aux-1);
        }
        else
        {
            if(mystack.content[mystack.top]==1)
            {
                direction=0;
            }
            else
            {
                if(aux1<n)
                {
                    aux1=mystack.content[mystack.top];
                    aux2=aux1*(aux1+1);
                    pop(&mystack,*x);
                    mystack.content[mystack.top]=aux2;
                }
            }
        }
    }
    cout<<endl<<mystack.content[0];
    return 0;
}

Answer 1

堆栈具有推送和弹出操作。 Push会在堆栈顶部添加一个新项目，pop会从堆栈顶部删除该项目并将其返回。对于阶乘的一些伪代码：

int factorial(int n) {
    Stack<int> stack;
    stack.push(1);

    for(int i=1; i<=n; ++i) {
       stack.push(stack.pop()*i);
    }
    return stack.pop();
}

Answer 2

使用解释器模式，它只是将n..2中的数字放在堆栈中（排除1，因为它是基本情况）

package main

import "github.com/ayalaio/utils/stack"

type MathFact struct {
    Content int
}

func (self *MathFact) FactorialFunc() func(int) int {
    return func(j int) int {
        return self.Content * j
    }
}

func main() {
    s := stack.New()

    factorialOf := 6

    curr := factorialOf

    for curr >= 2 {
        s.Add(&MathFact{curr})
        curr--
    }

    // 1 -> base case
    r := 1
    for s.Len() > 0 {
        e := s.Front()
        ff := e.Value.(*MathFact).FactorialFunc()
        r = ff(r)
        s.Remove()
    }
    println(r)
}

Answer 3

这就是我在没有递归的情况下对数字进行因式分解（使用堆栈）。

#include <iostream>
#include <stack>

using namespace std;

void main()
{
    stack<int> myStack;
    int userFactor, tempFactor, stackLoop;
    int runTotal = 0;

    cout << "Enter number to be factorialized: ";
    cin >> userFactor;
    tempFactor = userFactor;

    if (userFactor == 1 || userFactor == 0) //a "base case" of sorts
        cout << endl << userFactor << " factorialized is 1.\n";

    else
    {
        while (tempFactor > 1) //load the stack
        {
            myStack.push(tempFactor);
            tempFactor--;
        }

        runTotal = myStack.top(); //start unloading the stack
        myStack.pop();
        stackLoop = (int)myStack.size();

        for (int x = 0; x < stackLoop; x++) //multiply each 
        {
            runTotal *= myStack.top();
            myStack.pop();
        }
        cout << endl << userFactor << " factorialized is: " << runTotal << endl;
    }
}