Write c plus plus program of any desending number?

Answer 1

The problem with generating Fibonacci numbers is that they get large very fast. They will eventually exceed the range of even 64 bit integers. In C++, one way to solve this issue is to write a dynamic, arbitrary decimal class.

You could create a linked list, where each element represents a digit. The first element is the units digit, the second the tens digit, the third the hundreds digit, and so forth.

Imbed this linked list into a decimal number class, and provide operators to do various math operations such as addition between two instances of the class. When implementing operator+, for instance, iterate through the elements of both classes, adding them, and applying the carries in each step. If need be, invoke the AddDigit method of the linked list to make the r-value larger by one digit.

With this class, implementing construct, destruct, copy, assign, add, and print, you can generate a Fibonacci sequence using the algorithm of keeping three numbers, and iterating each sequence by adding the prior two numbers and then moving numbers around. (More efficient would be to rotate pointers to the three instances, rather than copying them.) As the instances get reused, it would also be helpful if you did not just delete elements, but, rather, allowed for them to be reused by keeping track of how many are in use versus how many are allocated. (Or you could just zero the excees digits. That is your choice, and it is part of your overall design. Keep in mind that you do know how long the list is, by knowing which element is the last element.)

As you develop this class, you will find more uses that involve other operations, such as multiply and divide. You can extend the class as necessary.

The following example demonstrates a very basic implementation that will generate Fibonacci numbers up to a given length (200 digits in the example, but you could easily generate arbitrary length from user input). The program can also be easily adapted to produce the nth Fibonacci. The implementation of the bignum class could be improved enormously by embedding a pointer to std::vector and implementing a move constructor (like a copy constructor, but ownership of the resources is swapped rather than shared). Also, storing one character per element is highly inefficient, it would be far better to store multiple digits in 64-bit elements. However I've kept the class as simple as possible for the purpose of clarity.

#include

#include

class bignum

{

friend std::ostream& operator<<(std::ostream& os, const bignum& n);

public:

bignum(unsigned int n=0);

bignum operator+(const bignum& );

size_t size()const{return(list.size());}

private:

std::list list;

};

bignum::bignum(unsigned int n)

{

if( n )do

{

unsigned char digit=n%10;

list.push_front( digit );

} while( n/=10 );

}

bignum bignum::operator+(const bignum& n)

{

bignum result;

unsigned char carry=0, digit=0;

std::list::const_reverse_iterator first = list.rbegin();

std::list::const_reverse_iterator second = n.list.rbegin();

while( first!=list.rend() second!=n.list.rend() carry )

{

digit=carry;

if( first!=list.rend() ) digit+=*first++;

if( second!=n.list.rend() ) digit+=*second++;

carry=digit/10;

digit%=10;

if( digit first!=list.rend() second!=n.list.rend() carry )

result.list.push_front( digit );

}

return( result );

}

std::ostream& operator<<(std::ostream& os, const bignum& n)

{

if( !n.list.size() )

os<<'0';

else for( std::list::const_iterator it=n.list.begin(); it!=n.list.end(); ++it )

os<<(unsigned int)*it;

return( os );

}

int main()

{

bignum* num1 = new bignum(0); std::cout<<*num1<

bignum* num2 = new bignum(1); std::cout<<*num2<

// generate the Fibonacci sequence up to a length of 200 digits

while(num2->size()<200)

{

bignum* num3 = new bignum( *num1+*num2 );

delete(num1);

num1 = num2;

num2 = num3; std::cout<<*num2<

}

delete( num2 ); num2 = NULL;

delete( num1 ); num1 = NULL;

std::cout<

}

Answer 2

template<typename T> void print_descending (std::vector<T> v)

{

// sort in ascending order

v.sort();

// print in reverse order

for (auto i = v.rbegin(); i!=v.rend(); ++i)

std::cout << (*i) << std::endl;

}

Answer 3

There are several ways to determine if a string is a palindrome or not. Typically, you must first ignore all spacing, capitalisation and punctutation within the string, which can be done by copying the string, character by character, ignoring all non-alphanumeric characters. You then point to the first and last characters in the modified string and, so long as both characters under the pointers are the same, work the pointers towards the middle of the string until the pointers either meet in the middle or they pass each other. That is, if the string has an odd count of characters, the pointers will meet at the middle character, otherwise they will pass each other. At that point you can say with certainty the string is a palindrome. If the characters under the pointers differ at any time, then the string is not a palindrome. This is fairly straightforward to program.

A more interesting problem is when you have to locate the longest palindrome within a string which is not itself a palindrome. For instance, the string "Madam, I'm Adam is a palindrome" is not a palindrome, but it does contain one: "Madam I'm Adam". In this case we cannot point to the first and last characters and work towards the middle. Instead, we have to test every possible substring of the string. We do this by starting at the first character and treat it as if it were actually the middle character of a palindrome, and then move our pointers to the left and right of this character while the characters match. When they no longer match, or one of the pointers has reached either end of the string, we store the longest palindrome found up to that point and then move onto the next character and treat it as the middle character. If we continue in this manner, treating every character as if it were the middle character of a palindrome, we will eventually locate the longest palindrome.

The problem with this approach is when the longest palindrome has an even number of characters instead of an odd number. To get around this we simply place a single space between each character, and treat each of those as being the middle character as well. When a palindrome is found, we simply remove the spaces. In this way we can use exactly the same algorithm to cater for both odd and even character palindromes.

The only remaining problem is when we wish to print the palindrome itself. Since this will be a substring of the original string, we cannot use the modified string we used to locate the palindrome. One way to get around that is to store the original positions of each letter in an array of indices, and use that array to determine where the substring lies with in the original string.

The following program demonstrates this technique in full. The key function is the ispalindrome() function, which accepts a lower-case copy of the string (including the original spacing an punctuation), and a vector that contains the indices of each letter within the string (ignoring puctuation and spacing), separated by -1 values (representing the implied spaces between each letter). The pos value tells the function which index of the vector is to be treated as the middle character of the potential palindrome, while x and y are output parameters that determine the start and end of the palindrome within the vector. The function returns true if a palindrome was found, and the x and y values can be used to extract the palindrome from the original string, using the indices stored in the vector. Note that when the search for a palindrome fails, we step back the x and y indices by one, and if the vector index is -1, then we step back another index. We then test the x and y values to see if they indicate a palindrome was found or not.

The strip() function is another key function. This generates the vector from the lower case copy of the original string. Although we could eliminate the -1 values at the start and end of the vector, it's simpler to just leave them in.

You will note that the program can cater for strings that are themselves palindromes, as well as strings that contain palindromes.

#include<iostream>

#include<string>

#include<vector>

using namespace std;

string input_string(string prompt)

{

cout<<prompt<<":\t";

string input;

getline(cin, input, '\n');

return(input);

}

void convert_tolower(string& s)

{

for(string::iterator i=s.begin(); i!=s.end(); ++i)

*i=tolower(*i);

}

vector<int> strip(const string& s)

{

vector<int> v;

v.push_back(-1);

for(int i=0; i<s.size(); ++i)

{

if((s[i]>='a' && s[i]<='z') (s[i]>='0' && s[i]<='9'))

{

v.push_back(i);

v.push_back(-1);

}

}

return(v);

}

bool ispalindrome(const string s, const vector<int> v, int pos, int& x, int& y)

{

for(x=pos,y=pos; x>=0 && y<v.size(); --x, ++y)

if( v[x]!=-1 && ( s[v[x]]!=s[v[y]] ))

break;

++x, --y;

if( v[x]==-1 )

++x, --y;

return(x>=0 && x<y && y-x>1);

}

int main()

{

string input;

while(1)

{

input=input_string("Enter a string");

if(input.size()==0)

break;

string copy(input);

convert_tolower(copy);

vector<int> v=strip(copy);

string pal;

int pos=0;

for(int i=0; i<v.size(); ++i)

{

int start=0, end=0;

if( ispalindrome( copy, v, i, start, end))

{

string tmp( input.substr(v[start],v[end]-v[start]+1));

if( tmp.size() > pal.size() )

{

pal = tmp;

pos = v[start];

}

}

}

if( pal.size() )

{

cout<<"Palindrome:\t";

for(int i=0; i<pos; ++i)

cout<<" ";

cout<<pal<<"\n"<<endl;

}

else

cout<<"The string contains no palindromes!\n"<<endl;

}

return(0);

}

Example output:

Enter a string: Madam, I'm Adam

Palindrome: Madam, I'm Adam

Enter a string: Madam, I'm Adam is a palindrome

Palindrome: Madam, I'm Adam

Enter a string: In girum imus nocte et consumimur igni

Palindrome: In girum imus nocte et consumimur igni

Enter a string: 0123456765432

Palindrome: 23456765432

Enter a string:

Press any key to continue . . .