c/c++基礎習題解決(3)--the 3n+1 problem -- 程序空间-- 编程爱好者博客

问题描述：
这是一个古老的猜想：给定任何一个正整数n，对它进行以下操作：
n是偶数：n=n/2
n是奇数：n=3*n+1
这样经过多步操作后，最后必定变为1
如对13进行操作： 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
一共经历了9次操作，则称13这个数的周期是9

输入：
多组测试数据，每组一行，一行里有两个数m和n，请你找出m和n之间（包括m,n）的周期最大的数的周期
其中m,n均小于1e5

输出：
m,n之间周期最大的数的周期，一个结果单独占一行

样例输入：
1 10
2 3
30 100

样例输出：
19
7
118

难度：very easy

習題來源:飞燕之家C/C++语言学习论坛

解決代碼:

// NPlusOnePro.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#define INT_UPLIMIT 1
#define INT_DOWNLIMIT 500

//foward declaration

//the prototype of functions

//check input's validation
bool IsLegalInput(int iSNum,int iENum);

//calculate every number's cycle
void CalculteCycle(int iSNum,int iENum,int *pSave,int iSize);

//calculate the number's cycle
int GetCycle(int iTheNum,int iCount);

//get the maxsimum number in cycle-array
int GetMaxCycle(int *pSave,int iSize);

int _tmain(int argc, _TCHAR* argv[])
{
int iStartNum=0,iEndNum=0;
int iIntervalNum=0;
int *pTemptResult=NULL;
int iResult=0;

while(scanf("%d %d",&iStartNum,&iEndNum))
{
    //check input's validation
    if(!IsLegalInput(iStartNum,iEndNum))
    {
     printf("input invalidate!");
     break;
    }

      //Initlization
         iIntervalNum=iEndNum-iStartNum+1;
         pTemptResult=(int *)malloc(iIntervalNum*sizeof(int));
         assert(pTemptResult!=NULL);
   memset(pTemptResult,0x00,iIntervalNum*sizeof(int));

    //start to deal with

          //calculate every number's cycle and conserve in ponter pTemptResult
    CalculteCycle(iStartNum,iEndNum,pTemptResult,iIntervalNum);
          //get the final result
    iResult=GetMaxCycle(pTemptResult,iIntervalNum);

//show result
printf("The Maximum Cycle in these numbers is:%d",iResult);
}

return 0;
}

//check input's validation
bool IsLegalInput(int iSNum,int iENum)
{
     if(iSNum<1||iENum<1)
   return false;
  if(iSNum>=iENum)
   return false;
  return true;
}

//calculate every number's cycle
void CalculteCycle(int iSNum,int iENum,int *pSave,int iSize)
{
     int      i=0,j=0;
        int      iCyTempt=0;
  int*    pIntAcc=pSave;

        for(i=iSNum;i<=iENum;i++)
  {
             iCyTempt=GetCycle(i,0);
    pSave[j]=iCyTempt;
    j++;
    if(j>=iSize)
     break;
  }
}

//calculate the number's cycle
int   GetCycle(int iTheNum,int iCount)
{
    if(iTheNum==1)
     return iCount;

    if(iTheNum%2==0)
     return GetCycle(iTheNum/2,iCount+1);
    else
     return GetCycle(iTheNum*3+1,iCount+1);
}

//get the maxsimum number in cycle-array
int    GetMaxCycle(int *pSave,int iSize)
{
   int i=0,iMaxValue=0;
   assert(pSave!=NULL);

   iMaxValue=pSave[0];
   for(i=1;i<iSize;i++)
   {
    if(pSave[i]>iMaxValue)
    iMaxValue=pSave[i];
   }
   return iMaxValue;
}

博客介绍

正文

c/c++基礎習題解決(3)--the 3n+1 problem2007-07-27 21:33:00

评论