Fibonacci Sequence
Problem Analysis
To correctly implement recursive function calls and returns, parameter passing and return address handling must be properly addressed. Specifically, during each recursive call, new storage space must be allocated for all parameters, while preserving the actual parameters from the previous call and the return address for the current call.
Algorithm Design
The algorithm is described as follows:
int Fib(int n){
int fib;
if(n==0) fib=0;
else if(n==1) fib=1;
else fib=Fib(n-1)+Fib(n-2);
return fib;
}
Data Structure Design
A stack is used to allocate and manage storage space. The system creates a “working record” for each procedure call, storing the values of all parameters before the call and the return address after the call. This working record is pushed onto the stack to ensure correct information retrieval upon return.
Debugging Process
During each function call, outputting the passed parameters provides a clearer visualization of the stack’s call process.
For example, in the initial recursive call Fib(2), the program first pushes Fib(5), Fib(4), …, Fib(1) onto the stack. When n == 1, the value is returned to the previous address. Similarly, when n == 0, its value is returned, allowing Fib(2) to compute its value, which is then returned to its caller Fib(3).
Output Result
Source Code
#include<bits/stdc++.h>
using namespace std;
int Fibonacci(int n){
int fib;
if(n==0){
fib=0;
}else if(n==1){
fib=1;
}else if(n==2){
fib=2;
}else{
fib=Fibonacci(n-1)+Fibonacci(n-2);
}
return fib;
}
int main(){
int n=0;
cout<<"Enter n:";
start:
cin>>n;
cout<<"The nth Fibonacci number is "<<Fibonacci(n)<<endl;
cout<<"Continue calculation? (y/n):";
char choice;
choice:
cin>>choice;
if(choice=='y'||choice=='Y'){
goto start;
}else if(choice=='n'||choice=='N'){
return 0;
}else{
cout<<"Invalid input, please re-enter:";
goto choice;
}
return 0;
}
Set Partitioning Problem
Problem Analysis
The task requires partitioning a set into mutually disjoint subsets such that no elements within any subset conflict with each other, while minimizing the number of subsets. Such problems are commonly encountered in scheduling applications.
Algorithm Design
Conflict relationships are represented using a 2D array, where 1 indicates a conflict and 0 indicates no conflict. A cyclic screening method is employed for partitioning: starting with the first element, it is isolated, and other elements are checked for conflicts with the isolated elements. Non-conflicting elements are grouped together. This process repeats until all mutually non-conflicting elements are grouped, iterating until all elements are partitioned.
Data Structure Design
A circular queue stores the data, allowing iterative processing without requiring additional storage space.
Debugging Process
Output Result
Source Code
#include<bits/stdc++.h>
using namespace std;
int newr[9];
void DivideIntoGroup(int n, int R[][9], int cp[], int result[]) {
int front, rear, group, pre, I, i;
front = n - 1;
rear = n - 1;
for (i = 0; i < n; i++) {
newr[i] = 0;
cp[i] = i + 1;
}
group = 1;
pre = 0;
do {
front = (front + 1) % n;
I = cp[front];
if (I < pre) {
group = group + 1;
result[I - 1] = group;
for (i = 0; i < n; i++) {
newr[i] = R[I - 1][i];
}
} else {
if (newr[I - 1] != 0) {
rear = (rear + 1) % n;
cp[rear] = I;
} else {
result[I - 1] = group;
for (i = 0; i < n; i++) {
newr[i] += R[I - 1][i];
}
}
}
pre = I;
} while (rear != front);
}
int main() {
int result[9], cp[9];
int R[9][9] = {
{0, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 1, 0, 1, 1, 0, 1},
{0, 1, 1, 0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 1, 0, 0, 0, 0},
};
DivideIntoGroup(9, R, cp, result);
for (int i = 0; i < 9; i++) {
cout << i + 1 << " ";
}
cout << endl;
for (int i = 0; i < 9; i++) {
cout << result[i] << " ";
}
return 0;
}
When will I have a drink and discuss the details again?