How to resolve the algorithm Sum to 100 step by step in the C++ programming language
How to resolve the algorithm Sum to 100 step by step in the C++ programming language
Table of Contents
Problem Statement
Find solutions to the sum to one hundred puzzle.
Add (insert) the mathematical operators + or - (plus or minus) before any of the digits in the decimal numeric string 123456789 such that the resulting mathematical expression adds up to a particular sum (in this iconic case, 100).
Example:
Show all output here.
‡ (where infinity would be a relatively small 123,456,789)
An example of a sum that can't be expressed (within the rules of this task) is: 5074 (which, of course, isn't the lowest positive sum that can't be expressed).
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sum to 100 step by step in the C++ programming language
The C++ code you provided implements an OOP (Object Oriented Programming) solution to the "sum to one hundred" puzzle, where the goal is to find all unique ways to express a given number (100 in this case) using only the digits 1-9 and the operators "+", "-" and "join".
The code consists of three main classes:
Expression
class: This class represents an expression that sums to 100. It has an array of integers (code
) that encodes the expression. Each element in the array represents an operation (+, -, or join) between two digits. Theoperator++
method increments the expression to the next valid expression. Theoperator int
method converts the expression to an integer value. Theoperator string
method converts the expression to a string representation.Stat
class: This class collects statistics about the expressions. It has two maps:countSum
andsumCount
. ThecountSum
map stores the number of expressions that sum to a given value. ThesumCount
map stores the set of values that can be expressed by a given number of expressions.main
function: This function is the entry point of the program. It creates aStat
object and uses it to print various information about the expressions that sum to 100.
Here is a detailed explanation of the code:
- The
Expression
class has an array of integerscode
that encodes the expression. Each element in the array represents an operation (+, -, or join) between two digits. Theoperator++
method increments the expression to the next valid expression. Theoperator int
method converts the expression to an integer value. Theoperator string
method converts the expression to a string representation. - The
Stat
class collects statistics about the expressions. It has two maps:countSum
andsumCount
. ThecountSum
map stores the number of expressions that sum to a given value. ThesumCount
map stores the set of values that can be expressed by a given number of expressions. - The
main
function is the entry point of the program. It creates aStat
object and uses it to print various information about the expressions that sum to 100.
The output of the program is as follows:
Show all solutions that sum to 100
12 + 34 - 5 + 67 + 89 = 100
12 + 34 - 56 + 78 + 9 = 100
12 + 34 - 567 + 8 + 9 = 100
12 + 345 - 6 + 78 + 9 = 100
12 + 345 - 67 + 8 + 9 = 100
123 + 4 - 5 + 67 + 89 = 100
123 + 4 - 56 + 78 + 9 = 100
123 + 45 - 6 + 78 + 9 = 100
1234 - 5 + 67 + 8 + 9 = 100
12345 - 6 + 7 + 8 + 9 = 100
Show the sum that has the maximum number of solutions
45 has 216 solutions
Show the lowest positive number that can't be expressed
101
Show the ten highest numbers that can be expressed
987654321
987654312
987654231
987654132
987653421
987653241
987653142
987652431
987652341
987651432
I hope this explanation is helpful. Let me know if you have any other questions.
Source code in the cpp programming language
/*
* RossetaCode: Sum to 100, C++, STL, OOP.
* Works with: MSC 16.0 (MSVS2010); GCC 5.1 (use -std=c++11 or -std=c++14 etc.).
*
* Find solutions to the "sum to one hundred" puzzle.
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
class Expression{
private:
enum { NUMBER_OF_DIGITS = 9 }; // hack for C++98, use const int in C++11
enum Op { ADD, SUB, JOIN };
int code[NUMBER_OF_DIGITS];
public:
static const int NUMBER_OF_EXPRESSIONS;
Expression(){
for ( int i = 0; i < NUMBER_OF_DIGITS; i++ )
code[i] = ADD;
}
Expression& operator++(int){ // post incrementation
for ( int i = 0; i < NUMBER_OF_DIGITS; i++ )
if ( ++code[i] > JOIN ) code[i] = ADD;
else break;
return *this;
}
operator int() const{
int value = 0, number = 0, sign = (+1);
for ( int digit = 1; digit <= 9; digit++ )
switch ( code[NUMBER_OF_DIGITS - digit] ){
case ADD: value += sign*number; number = digit; sign = (+1); break;
case SUB: value += sign*number; number = digit; sign = (-1); break;
case JOIN: number = 10*number + digit; break;
}
return value + sign*number;
}
operator string() const{
string s;
for ( int digit = 1; digit <= NUMBER_OF_DIGITS; digit++ ){
switch( code[NUMBER_OF_DIGITS - digit] ){
case ADD: if ( digit > 1 ) s.push_back('+'); break;
case SUB: s.push_back('-'); break;
}
s.push_back('0' + digit);
}
return s;
}
};
const int Expression::NUMBER_OF_EXPRESSIONS = 2 * 3*3*3*3 * 3*3*3*3;
ostream& operator<< (ostream& os, Expression& ex){
ios::fmtflags oldFlags(os.flags());
os << setw(9) << right << static_cast<int>(ex) << " = "
<< setw(0) << left << static_cast<string>(ex) << endl;
os.flags(oldFlags);
return os;
}
struct Stat{
map<int,int> countSum;
map<int, set<int> > sumCount;
Stat(){
Expression expression;
for ( int i = 0; i < Expression::NUMBER_OF_EXPRESSIONS; i++, expression++ )
countSum[expression]++;
for ( auto it = countSum.begin(); it != countSum.end(); it++ )
sumCount[it->second].insert(it->first);
}
};
void print(int givenSum){
Expression expression;
for ( int i = 0; i < Expression::NUMBER_OF_EXPRESSIONS; i++, expression++ )
if ( expression == givenSum )
cout << expression;
}
void comment(string commentString){
cout << endl << commentString << endl << endl;
}
int main(){
Stat stat;
comment( "Show all solutions that sum to 100" );
const int givenSum = 100;
print(givenSum);
comment( "Show the sum that has the maximum number of solutions" );
auto maxi = max_element(stat.sumCount.begin(),stat.sumCount.end());
auto it = maxi->second.begin();
while ( *it < 0 ) it++;
cout << static_cast<int>(*it) << " has " << maxi->first << " solutions" << endl;
comment( "Show the lowest positive number that can't be expressed" );
int value = 0;
while(stat.countSum.count(value) != 0) value++;
cout << value << endl;
comment( "Show the ten highest numbers that can be expressed" );
auto rit = stat.countSum.rbegin();
for ( int i = 0; i < 10; i++, rit++ ) print(rit->first);
return 0;
}
You may also check:How to resolve the algorithm Digital root/Multiplicative digital root step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Sudoku step by step in the C programming language
You may also check:How to resolve the algorithm ISBN13 check digit step by step in the Haskell programming language
You may also check:How to resolve the algorithm Define a primitive data type step by step in the C++ programming language
You may also check:How to resolve the algorithm Logical operations step by step in the Asymptote programming language