代码如下
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void)
{
int n;//The number of random numbers generated
int a[1000] = {0};//[1000] indicates that there are 1000 0s in the array a[]
int b[1000];
int loop_times;//loop_times means the times of loop
printf("Please enter the length of the array n: ");
scanf("%d",&n);//Use scanf to enter the random number n that needs to be generated
for ( loop_times = 0; pow(2,loop_times) <= n; loop_times++){}//for loop: in order to calculate the maximum quadratic power in n
loop_times--;//Subtract the result by 1, and get the power of 2 at the end interval of the up phase
srand((unsigned)time(NULL));//Initialize random seed
for (int i = 0; i < n; i++)//For loop randomly generate n random numbers and assign them to a[0],a[1],...,a[n-1]
{
a[i] = rand()%20;//Limit the generated random number to less than 20
b[i] = a[i];//Let b[i] = a[i]
}
printf("\n");
int x;//x used to limit the power of 2
int interval;//interval means the step
int middle_number;//"middle_number"means the number used for calculation in the formula
if (n & (n - 1)){//if n is not the power of 2
printf("\nUp Phase\n");
for(int i = 0; i < pow(2, loop_times + 1);i++)//for loop:print the random array b[i]
printf("%5d ", b[i]);//For beauty, each number occupies 5 digits so that each row of numbers can be aligned
printf("\n");
for(x = 1; x <= loop_times + 1; x++){//for loop:limit the array no bigger than loop_times + 1,and fill in the missing digits with 0
interval = pow(2, x);//interval means step
middle_number = pow(2, x - 1);//middle_number always equal to the interval divided by 2(according to the law in the example).
for(int i = 0; i < pow(2, loop_times + 1); i++)//for loop:make a calculation
if (i % interval == interval - 1)//Let the formula be calculated only in a specified number of digits
b[i] = b[i - middle_number] + b[i];//The formula
for (int i = 0; i < pow(2, loop_times + 1); i++)//for loop:print the result
{
printf("%5d ", b[i]);
}
printf("\n");
}//End of the up phase
printf("\nDown Phase\n");
for (int i = 0; i < pow(2, loop_times + 1); i++)//for loop: print the result of up phase again
{
printf("%5d ", b[i]);
}
printf("\n");
for (x = 0; x < loop_times + 1; x++){
interval = pow(2, loop_times + 1 - x);
middle_number = pow(2, loop_times - x);
for(int i = 0; i < pow(2, loop_times + 1); i++){
if(i % interval == interval - 1){
b[i + middle_number] = b[i + middle_number] + b[i];
}
}
for (int i = 0; i < pow(2, loop_times + 1); i++)//for loop
{
printf("%5d ", b[i]);
}
printf("\n");
}
}
else{//if n is the power of 2
printf("\nUp Phase\n");
for(int i = 0; i < n;i++)//for loop:print the random array b[i]
printf("%5d ", b[i]);
printf("\n");
for(x = 1; x < loop_times + 1; x++){
interval = pow(2, x);
middle_number = pow(2, x - 1);
for(int i = 0; i < n; i++)
if (i % interval == interval - 1)
b[i] = b[i - middle_number] + b[i];
for (int i = 0; i < n; i++)
printf("%5d ", b[i]);
printf("\n");
}
printf("\n");
}
printf("\nDown Phase\n");
for (x = 0; x < loop_times + 1; x++){
interval = pow(2, loop_times + 1 - x);
middle_number = pow(2, loop_times - x);
for(int i = 0; i < n; i++){
if(i % interval == interval - 1){
b[i + middle_number] = b[i + middle_number] + b[i];
}
}
for (int i = 0; i < n; i++)
{
printf("%5d ", b[i]);
}
printf("\n");
}
return 0;//Complete this function successfully
}
