pex10_7.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

// determine the of n-digit binary numbers
// that do not have two 1's in a row
long NoTwoOnes(long n)
{
	// if n is 1, there are 2 numbers (0,1)
	// stopping condition
	if (n == 1)
		return 2;
	else
	// if n is 2, there are 3 numbers (00,01,10)
	// stopping condition
	if (n == 2)
		return 3;
	else
		// recursive step. 0xx...xx ==>NoTwoOnes(n-1) numbers
		// 10xx...xx ==> NoTwoOnes(n-2) numbers. total is sum
		// of these two terms
		return NoTwoOnes(n-2) + NoTwoOnes(n-1);
}

void main(void)
{
	int n;
	
	// input n
	cout << "Enter n: ";
	cin >> n;
	
	// use NoTwoOnes to print the number of n-bit binary numbers
	// that do not have two 1's in a row
	cout << "The number of " << n
		 << " bit numbers not having two ones in a row = "
		 << NoTwoOnes(n) << endl;
}

/*
<Run>

Enter n: 8
The number of 8 bit numbers not having two ones in a row = 55
*/