C++ Blah Sequence
Description
The great mathematician Gauss discovered an interesting set of natural numbers called Blah during his childhood. The set Ba defined with base a is as follows:(1) a is the base of set Ba, and a is the first element of Ba;(2) If x is in set Ba, then both 2x + 1 and 3x + 1 are also in set Ba;(3) No other elements are in set Ba.Now, young Gauss wants to know what the N-th element would be if the elements of set Ba are arranged in ascending order.
Input Description
The input consists of two numbers, the base a (1 <= a <= 50) and the desired element index n (1 <= n <= 1000000).
Output Description
The output is the value of the n-th element in set Ba.
Sample Input 1
1 8Sample Output 1
15
Problem Solving Approach
Assuming the input is <span>1 5</span> (initial term is 1, generating the first 5 terms):
-
Initial: an=1
-
Second term:
-
q1: 1*2+1=3
-
q2: 1*3+1=4
-
Take the smaller one, 3
Third term:
-
q1: 3*2+1=7 (q1 now has 7)
-
q2: 3*3+1=10 (q2 now has 4,10)
-
Take the smaller one, 4
Fourth term:
-
q1: 4*2+1=9 (q1 now has 7,9)
-
q2: 4*3+1=13 (q2 now has 10,13)
-
Take the smaller one, 7
Fifth term:
-
q1: 7*2+1=15 (q1 now has 9,15)
-
q2: 7*3+1=22 (q2 now has 10,13,22)
-
Take the smaller one, 9
Finally, output the fifth term: 9
This algorithm effectively merges two generated sequences, ensuring that the next smallest valid number is obtained each time.
Code Sharing
/* * This program generates a special sequence, the sequence rules: * 1. The initial term is an * 2. Each subsequent term is the smaller of the two numbers obtained from the previous term through the transformations (2x+1 and 3x+1) * 3. When the results of the two transformations are the same, only one is taken * Input: initial term an and the number of terms to generate n * Output: the n-th term of the sequence */#include<bits/stdc++.h>using namespace std; queue<int> q1; // Stores candidate numbers generated by 2x+1 transformationqueue<int> q2; // Stores candidate numbers generated by 3x+1 transformation int main(){ int an, n; cin >> an >> n; // Input initial term and the number of terms to generate // Start generating from the second term until the n-th term for(int i = 2; i <= n; i++){ // Generate two new candidate numbers based on the current an q1.push(an * 2 + 1); q2.push(an * 3 + 1); // Choose the smaller number from the front of the two queues as the next an if(q1.front() > q2.front()){ an = q2.front(); q2.pop(); // Only consume the number from q2 } else if(q1.front() < q2.front()){ an = q1.front(); q1.pop(); // Only consume the number from q1 } else { // Case where both numbers are equal an = q1.front(); q1.pop(); // Consume numbers from both queues q2.pop(); } } cout << an; // Output the n-th term return 0;}
Click the blue text to follow immediately
