7-18 finding the single root of polynomial by dichotomy (20 points)

The principle of finding the function root by dichotomy is: if the continuous function f(x) takes different signs at the two endpoints of the interval [a,b], that is, f (a) f (b) < 0, then it has at least one root r in this interval, that is, f(r)=0.

The steps of dichotomy are:

• Check the interval length. If it is less than the given threshold, stop and output the midpoint of the interval (a+b)/2; otherwise
• If f (a) f (b) < 0, calculate the value f((a+b)/2) of the midpoint;
• If f((a+b)/2) is exactly 0, then (a+b)/2 is the required root; otherwise
• If f((a+b)/2) and f(a) have the same sign, it means that the root is in the interval [(a+b)/2,b], make a=(a+b)/2, and repeat the cycle;
• If f((a+b)/2) and f(b) have the same sign, it means that the root is in the interval [a,(a+b)/2], make b=(a+b)/2, and repeat the cycle.

This topic requires writing a program to calculate the root of a given third-order polynomial f(x)=a3 x3+a2 x2+a1 x+a0 in a given interval [a,b].

Input format:

Input the four coefficients a3, a2, a1 and a0 of the polynomial in the first line, and the interval endpoints A and b in the second line. The problem is to ensure that the polynomial has a unique single root in a given interval.

Output format:

Output the root of the polynomial in the interval in one line, accurate to 2 decimal places.

Example: "> example:" > input example:

3 -1 -3 1
-0.5 0.5

 

Output example:

0.33

#include <stdio.h>
double a3, a2, a1, a0;//Used in both functions, put it on the outside
double f(double x);
int main()
{
    double  y1, y2, y3;
    double a, b;
    scanf("%lf %lf %lf %lf", &a3, &a2, &a1, &a0);
    scanf("%lf %lf", &a, &b);
    
    while(b - a > 0.01 && f(a) * f(b) <= 0)//If the threshold is set by yourself, 0.1 will be wrong, and 0.01 will be displayed correctly and commensurate with the output of two decimal places
//When the zero point is at the endpoint, the product will be zero
    {
        y1 = f(a);
        y2 = f(b);
        y3 = f((a + b) / 2);
            if(y3 == 0)
                break;
            else if(y3 * y1 > 0)
            {
                a = (a + b) / 2;
            }
            else if(y3 * y1 < 0)
            {
                b = (a + b) / 2;
            }
        
    }
    printf("%.2lf", (a + b) / 2);
    return 0;
}
double f(double x)
{
    return a3 * x * x * x + a2 * x * x + a1 * x + a0;
}

7-27 bubble sorting (20 points)

The bubble sorting method of sorting n integers from small to large works like this: compare two adjacent elements from beginning to end, and exchange them if the previous element is larger than the following element. Through one scan, the last element must be the largest element. Then scan the first n − 1 elements for the second time in the same way. And so on. Finally, only two elements need to be processed to complete the sorting of N numbers.

This problem requires that for any given K (< n), the intermediate result sequence after the k-th pass of scanning shall be output.

Input format:

Input: N and K (1 ≤ K < n ≤ 100) are given in line 1, and N integers to be sorted are given in line 2. The numbers are separated by spaces.

Output format:

Output the intermediate result sequence after the K-th pass of the bubble sorting method in one line. The numbers are separated by spaces, but there shall be no redundant spaces at the end.

Input sample:

6 2
2 3 5 1 6 4

Output example:

2 1 3 4 5 6

//The algorithm forgot how to write

#include <stdio.h>
int main()
{
    int n, k, a[100], i, j, temp, t;
    scanf("%d %d", &n, &k);
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for(i = 0; i < k; i++)//Sort k times
    {
        for(j = 0; j < n - 1 - i; j++)//The ordered elements are no longer compared
        {
            if(a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        
     }      
    for(i = 0; i < n; i++)
            {
                if(i == 0)
                    printf("%d", a[i]);
                else
                    printf(" %d", a[i]);
            }
        
   
    return 0;
}

7-30 bubble sorting of strings (20 points)

We already know the bubble sorting method of sorting N integers from small to large. This problem requires that this method be used for string sequence, and for any given K (< N), output the intermediate result sequence after scanning the k-th pass.

Input format:

Input N and K (1 ≤ K < N ≤ 100) are given in the first line, and then N lines contain a non empty string with a length of no more than 10 and only composed of lowercase English letters.

Output format:

Output the intermediate result sequence after the K-th pass of bubble sorting scanning, and each line contains a string.

Input sample:

6 2
best
cat
east
a
free
day

Output example:

best
a
cat
day
east
free

//The variables in strcmp and strcpy are pointer type, and temp should be an array

#include <stdio.h>
#include <string.h>
int main()
{
    int n, k, i, j;
    scanf("%d %d", &n, &k);
    char a[n][11], temp[11];
    
    for(i = 0; i < n; i++)
        scanf("%s", a[i]);
    for(i = 0; i < k; i++)
    {
        for(j = 0; j < n - 1 - i; j++)
        {
            if(strcmp(a[j],a[j + 1]) > 0)
            {
                strcpy(temp, a[j + 1]);
                strcpy(a[j + 1], a[j]);
                strcpy(a[j], temp);
              
            }
        }
    }
    for(i = 0; i < n; i++)
        printf("%s\n", a[i]);
}