每次爬楼梯有每次可跨1,2,3步,爬上一个N阶楼梯有多少种方式,打印出每种方式。
// ConsoleApplication6.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <map>
using namespace std;
typedef std::vector<int> VecStep;
typedef std::map<int, VecStep> MapWay;
VecStep m_vecCanStep;
VecStep m_vecNextStep;
MapWay m_mapWay;
int iSum = 0;
void wayPrint()
{
for (auto it = m_mapWay.begin(); it != m_mapWay.end(); it++)
{
int iSize = it->second.size();
for (int i = 0; i < iSize; i++)
{
printf("%d ", it->second[i]);
}
printf("\n");
}
}
void creep(int iLeftStep, int iNextStep, int iCnt)
{
for (int i = 0; i < (int)m_vecCanStep.size(); i++)
{
if (iNextStep == m_vecCanStep[i])
{
int iStepSize = m_vecNextStep.size();
if (iCnt >= iStepSize)
{
m_vecNextStep.push_back(iNextStep);
}
else if (iCnt < iStepSize)
{
m_vecNextStep[iCnt] = iNextStep;
}
iCnt++;
}
}
if (iLeftStep == 0)
{
VecStep vecStep;
for (int i = 0; i < iCnt; i++)
{
vecStep.push_back(m_vecNextStep[i]);
}
m_mapWay.insert(MapWay::value_type(iSum, vecStep));
iSum++;
}
for (int i = 0; i < (int)m_vecCanStep.size(); i++)
{
if (iLeftStep - m_vecCanStep[i] >= 0)
{
creep(iLeftStep - m_vecCanStep[i], m_vecCanStep[i], iCnt);
}
}
}
void main()
{
int iTotalStep = 0;
int iNextStep = 0;
int iStepCnt = 0;
m_vecCanStep.push_back(1);
m_vecCanStep.push_back(2);
m_vecCanStep.push_back(3);
scanf_s("%d", &iTotalStep);
creep(iTotalStep, iNextStep,iStepCnt);
wayPrint();
printf("TotalWay = %d", iSum);
}
m_vecCanStep:每次可以走的步数,插入1,2,3
m_vecNextStep:从0-iCnt为每种可以达到的N阶的走法的步骤
m_mapWay:所有的走法
Creep形参含义:iLeftStep剩余总阶数,iNextStep下一步走法(1,2,3),iCnt当前走法已经走过的步骤统计