Do this problem (both parts) in C++. Provide proper commenting (this is crucial)

Question

Do this problem (both parts) in C++. Provide proper commenting (this is crucial) and make sure it compiles and runs well with NO ERRORS. Write a function that takes as parameters three numbers. The first number is the congruence class. The second number is the modulus, i.e., the number we divide by, and the third number is the cutoff. For example, congruence(1, 2, 10) finds all members of the congruence class of 1 modulo 2 less than 10, which in this case is (starting from 1) {1, 3, 5, 7, 9}. As you can notice, any element divided by 2 will have remainder 1. Another example is congruence(0, 3, 14). In this case, we return {0, 3, 6, 9, 12}. One final example is congruence(3, 10, 100). In this case, we return {3, 13, 23, 33, 43, 53, 63, 73, 83, 93}. The Chinese Remainder Theorem deals with modulo (think remainder) arithmetic. For example, suppose we have the list of numbers {3, 4, 5}. These numbers are pairwise coprime. Now suppose we want to find a number X such that the following holds true: The remainder of X/3 is 2. The remainder of X/4 is 3. The remainder of X/5 is 1. we can calculate x, which is the purpose of the Chinese Remainder Theorem, by using the congruence classes function defined in part 1 with the cutoff set to 3 * 4 * 5 = 60. In this case, we have the following: congruence(2, 3, 60) = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59} congruence (3, 4, 60) = (3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59} congruence(1, 5, 60) (1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56} The X that solves this problem is 11, which happens to be the smallest intersection of the three sets, Note that 11 mod 3 is 2, 11 mod 4 is 3, and 11 mod 5 is 1. For this problem, you need to calculate X where the function parameters are the list of moduli and the list of remainders In the above example, the function can be called in MATLAB as crt([3 4 5], [2 3 1]), which will return 11 given the example above. If the list of numbers passed are not pairwise coprime, return -1 (or some other sentinel value) to indicate that the Chinese remainder theorem is not applicable.

Explanation / Answer

#include <iostream>

using namespace std;
static int cnt=0; //satic variable o track the index array length
// function to generate and retrun random numbers.
int * congruence( int cngrnce,int modulus,int cutoff) {
static int r[100]; //static array to store values
for(int i=0;i<=cutoff;i++){
       if((i%modulus)==cngrnce){ //check if the value is congruence class if true pull to array and increment cnt as we are storing in array,incrementing index
           r[cnt]=i;
//cout<<r[i]<<endl;
           cnt++;
       }
}
return r; //return aray

}

int main () {
// a pointer to an int.
int *p;
int cngrnce,modulus,cutoff;//read the three values
cout<<"Enter three numbers:"<<endl;
   cin>>cngrnce>>modulus>>cutoff; //read the three values
p = congruence(cngrnce,modulus,cutoff);
cout<<"congruence("<<cngrnce<<","<<modulus<<","<<cutoff<<") = {";
for ( int i = 0; i < cnt; i++ ) {
cout << *(p + i)<<" ";
}
cout<<"} ";

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.