1: //binary_search2a.cpp
3: #include <iostream>
4: #include <vector>
5: #include <algorithm>
6: using namespace std;
8: /**
9: Tests if one integer has a smaller digit sum than another.
10: Pre:\n i1 and i2 have been initialized and i1, i2 are both > 0.
11: Post:\n Returns true if sum of the digits in i1 is < sum of digits
12: in i2, and otherwise returns false.
13: */
14: bool hasSmallerDigitSum
15: (
16: int i1, //in
17: int i2 //in
18: )
19: {
20: int digitSum1 = 0;
21: while (i1 != 0)
22: {
23: digitSum1 += i1 % 10;
24: i1 /= 10;
25: }
27: int digitSum2 = 0;
28: while (i2 != 0)
29: {
30: digitSum2 += i2 % 10;
31: i2 /= 10;
32: }
33: return digitSum1 < digitSum2;
34: }
36: int main()
37: {
38: cout << "\nThis program illustrates the use of the STL "
39: "binary_search() algorithm (extended\nversion) to determine "
40: "whether an integer having the same digit sum as a given "
41: "\ninteger exists among the integers in a vector of integers. "
42: "The integer values\nbeing searched are assumed to be ordered "
43: "in the sense that an integer with a\nsmaller digit sum "
44: "precedes one with a larger digit sum.";
45: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
47: int a[] = {21, 13, 31, 40, 5, 51, 25, 52, 70,
48: 8, 62, 71, 45, 54, 55, 82, 38, 56,
49: 65, 92, 39, 48, 75, 49, 59, 88};
51: vector<int> v(a, a+26);
52: cout << "\nHere are the values in the vector:\n";
53: for (vector<int>::size_type i=0; i<v.size(); i++)
54: cout << v.at(i) << " ";
55: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
57: if (binary_search(v.begin(), v.end(), 11, hasSmallerDigitSum))
58: cout << "\nA value with the same digit sum as 11 was found.";
59: else
60: cout << "\nA value with the same digit sum as 11 was not found.";
61: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
63: if (binary_search(v.begin(), v.end(), 13, hasSmallerDigitSum))
64: cout << "\nA value with the same digit sum as 13 was found.";
65: else
66: cout << "\nA value with the same digit sum as 13 was not found.";
67: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
69: if (binary_search(v.begin(), v.end(), 31, hasSmallerDigitSum))
70: cout << "\nA value with the same digit sum as 31 was found.";
71: else
72: cout << "\nA value with the same digit sum as 31 was not found.";
73: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
75: if (binary_search(v.begin(), v.end(), 41, hasSmallerDigitSum))
76: cout << "\nA value with the same digit sum as 41 was found.";
77: else
78: cout << "\nA value with the same digit sum as 41 was not found.";
79: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
81: if (binary_search(v.begin(), v.end(), 77, hasSmallerDigitSum))
82: cout << "\nA value with the same digit sum as 77 was found.";
83: else
84: cout << "\nA value with the same digit sum as 77 was not found.";
85: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
87: if (binary_search(v.begin(), v.end(), 78, hasSmallerDigitSum))
88: cout << "\nA value with the same digit sum as 78 was found.";
89: else
90: cout << "\nA value with the same digit sum as 78 was not found.";
91: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
92: }