Professional course - Code question record

Catalog

Divide a positive integer into prime factors   The notes P25

division   The notes P30

Give the date of year , Calculate the day of the year The notes P32

Explanation of binary conversion The notes P56

Print set M In front of 100 The lowest decimal   The notes P59

Enter a positive integer n, Print all subsets of the set   The notes P61

Find the number of all elements as M Subset   The notes P67

Realize the conversion between any two non negative integers with different base numbers The notes P68

Swap the positions of two vectors   The notes P80

---

Divide a positive integer into prime factors   The notes P25

Example ：

int main()
{
    int i, n;
    cout << " Please enter a number ：";
    cin >> n;
    cout << n << " = ";
    // Why i++？ Than i Can't small numbers be new n Quality factor of ？
    // The answer is no , Because if you compare i If the small number is n The quality factor of , It was already broken down 
    // In fact, in this algorithm , The decomposed prime factor increases from small to large 
    for (i = 2; i < n; i++)
    {
        while (n != i)  // if n == i, be n The prime factor of is n In itself 
        {
            // There is no need to judge i Is it a prime number , Because according to the characteristics of this algorithm , In case of i Before ,n About China i The factors of have been decomposed ,
            // In case of 6 This must have been done before 6 Break it down to 2*33, In case of 9 It must have been 9 Break it down to 3*3
            // So here's i It must be a prime number 
            if (n % i == 0) // if i It's the prime factor , Then print i
            {
                cout << i << " * ";
                n = n / i;
            }
            else break;     // If it can't be i to be divisible by , Consider i + 1
        }
    }
    cout << n;  // Print the last prime factor , That is to say n == i Prime factor of time 
    return 0;
}

  Print as follows ：

 

division   The notes P30

Non recursive writing ：

int gcd(int a, int b)
{
    int r;
    while (b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

A simpler recursive approach ：

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

Give the date of year , Calculate the day of the year The notes P32

According to the writing on the handout , The main reason is that the robustness judgment of data is very cumbersome

/*
 Not a whole century ： Can be 4 Divided by leap year .
 A hundred years ： Can be 400 Divided by leap years .
*/
int is_leapyear(int year)
{
    if (year % 400 == 0 || year % 4 == 0 && year % 100 != 0)
    {
        return 1;
    }
    return 0;
}
 
// Judge which day this year it is 
int whichday(int year, int month, int day)
{
    int mon[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    mon[2] = is_leapyear(year); // If it's a leap year , Add... In February 1 God 
    int count = 0;
    for (int i = 1; i < month; i++)
    {
        count += mon[i];
    }
    count += day;
    return count;
}
 
int main()
{
    int year, month, day;
    cout << " Please enter the year " << endl;
    while (1)
    {
        cin >> year;
        if (year < 0)
        {
            cout << " Month must be non negative , Please re-enter " << endl;
            continue;
        }
        break;
    }
 
    cout << " Please enter the month " << endl;
    while (1)
    {
        cin >> month;
        if (month < 1 || month > 12)
        {
            cout << " The month must be 1 To 12 Between " << endl;
            continue;
        }
        break;
    }
 
    cout << " Please enter the number of days " << endl;
    while (1)
    {
        cin >> day;
        if (day < 1)
        {
            cout << " Days cannot be less than 1" << endl;
            continue;
        }
        if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
        {
            if (day > 31)
            {
                cout << " The number of days you entered is greater than " << month << " The maximum number of days in a month " << endl;
                continue;
            }
        }
        else if (month == 2)
        {
            if (is_leapyear(year) == 1 && day > 29) // If it's a leap year 
            {
                cout << " The number of days you entered is greater than " << month << " The maximum number of days in a month " << endl;
                continue;
            }
            else if (is_leapyear(year) == 0 && day > 28)    // If it's not a leap year 
            {
                cout << " The number of days you entered is greater than " << month << " The maximum number of days in a month " << endl;
                continue;
            }
        }
        else
        {
            if (day > 30)
            {
                cout << " The number of days you entered is greater than " << month << " The maximum number of days in a month " << endl;
                continue;
            }
        }
        break;
    }
    printf("%d year %d month %d Day is the... Of the year %d God ", year, month, day, whichday(year, month, day));
    return 0;
}

 

Explanation of binary conversion The notes P56

Print set M In front of 100 The lowest decimal   The notes P59

The code on the handout is not well written , So I found this interesting way of writing on the Internet , This method adopts the idea of merging and sorting ：

        The difficulty of this problem is that it is difficult to determine the smallest n What is the number n Number , Now let's assume that int Type y and z Look at two " Array ",y The record is 2 * a[0] + 1、 2 * a[1] + 1、 2 * a[2] + 1....,z The record is  3 * a[0] + 1、 3 * a[1] + 1、 3 * a[2] + 1...., as long as a Is an increasing array ,y and z They are all increasing " Array ", Then you can use the idea of merging and sorting , Every comparison y and z Size , Select a smaller value to enter a Array , And then update y or z Value .

int main()
{
    int a[100];
    a[0] = 1;
    int i = 0, j = 0;   //i by y" Array " The pointer to ,j by z" Array " The pointer to 
    int y = 3, z = 4;   //y" Array " The first element of is 2 * a[0] + 1 = 3,z" Array " The first element of is 3 * a[0] + 1 = 4

    // Sort like merge 
    for (int k = 0; k < 100; k++)
    {
        if (y < z)
        {
            a[k] = y;
            y = 2 * a[i] + 1;   //y" Array " Move to the next element 
            i++;
        }
        else if (y == z)        // Because of the set heterogeneity , So when the values on both sides are equal, only one , On both sides " Array " All moving 
        {
            a[k] = y;
            y = 2 * a[i] + 1;
            i++;
            z = 3 * a[j] + 1;
            j++;
        }
        else
        {
            a[k] = z;
            z = 3 * a[j] + 1;   //z" Array " Move to the next element 
            j++;
        }
    }
    
    for (int i = 0; i < 100; i++)
    {
        if (i % 10 == 0) cout << endl;
        printf("%4d ", a[i]); 
    }
    return 0;
}

The results are as follows ：

Enter a positive integer n, Print all subsets of the set   The notes P61

Actually, bit operation is used , It is a method that I am weak in mastering .

For numbers 0 ~ n-1 for , Each number in a subset has two states ： Being and not being , So the combination of all States is a subset of all States , And we can see that the input positive integer is n, The number of subsets has 2 ^ n individual .

Based on the above , We can use binary numbers to represent all subsets ,1 Indicates presence ,0 Does not exist .

For example, the input 3, Then the total number of subsets is 2^3 = 8 individual , The set is {0, 1, 2}. And binary numbers also have 8 individual , for example 001 Corresponding subset {2},010 Corresponding subset {1},011 Corresponding subset {1, 2}.

void powerset(int n)
{
    int m = pow(2, n);  // share 2^n Seed set , Corresponding 2^n Binary number 
    int* subset = new int[n];   // Record subset 
    int len;    // Record the length of each generated subset 
    for (int i = 0; i < m; i++)     // Great circulation , Traverse 2^ Binary number , determine 2^n Seed set 
    {
        len = 0;
        for (int j = 0; j < n; j++) // Traversal numbers 0 ~ n-1, Check whether each number exists in the current subset 
        {
            int tmp = 1 << j;       // take 1 Move left j position , use tmp To check the j Whether numbers exist in the current subset 
            if (i & tmp)
            {
                subset[len++] = j;  // If it exists, record 
            }
        }
        cout << "{";
        for (int j = 0; j < len; j++)
        {
            cout << subset[j];
            if (j < len - 1) cout << ", ";
        }
        cout << "}" << endl;
    }
}

int main()
{
    int n;
    cin >> n;
    powerset(n);
    return 0;
}

Output is as follows ：

 

Find the number of all elements as M Subset   The notes P67

It's a bit troublesome to write this problem with the bit operation on the handout , It can be used directly dfs To write . Here, I directly let the elements in the original set be 1 ~ N - 1 了 .

int subset[100];
//N Is the number of elements in the set ,M Indicates that the number of elements required is M Subset 
//cur Array is used to hold the elements in the current subset ,len by cur The current number of elements in the array 
//index Indicates that the current cycle needs to be subscripted from index Start traversing the elements of 
// Every call dfs function , Will determine the current subset len The element of location 
void dfs(int cur[], int len, int M, int index, int N)
{
    // If the number of elements in the current subset is M, Print 
    if (len == M)
    {
        cout << "{";
        for (int i = 0; i < M; i++)
        {
            cout << cur[i];
            if (i < len - 1) cout << ", ";
        }
        cout << "}" << endl;
        return;
    }
    for (int i = index; i < N; i++)
    {
        cur[len] = subset[i];
        dfs(cur, len + 1, M, i + 1, N);
    }
}

int main()
{
    int N, M;    
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        subset[i] = i + 1;
    }
    int cur[100];    
    dfs(cur, 0, M, 0, N);
    return 0;
}

Output is as follows ：

About dfs The traversal in the function I originally wrote is like this ：

    for (int i = index; i < N; i++)
    {
        // selection 
        cur[len] = subset[i];
        dfs(cur, len + 1, M, i + 1, N);
        // Don't select 
        dfs(cur, len, M, i + 1, N);
    }

about cur[i], It can be divided into two cases: select and unselect , But this will cause the same subset to be printed repeatedly , For example, assemble {1,2,3}, If you write like this , Will print subsets repeatedly {2,3} two .

And the following correct way of writing , Its function can be understood as each call dfs Function time , Determine subset len The element of location , That is to say, every time you decide cur[len] Value , In this way, it can be ensured that in the position 0~M - 1 On , Elements in each position do not appear repeatedly

    for (int i = index; i < N; i++)
    {
        cur[len] = subset[i];
        dfs(cur, len + 1, M, i + 1, N);
    }

Realize the conversion between any two non negative integers with different base numbers The notes P68

This problem requires the ability to input multiple sets of test data , So let's see c++ How to input multiple groups of data in ：

int a;
string s;
while (cin >> a >> s)
{
    cout << a << " " << s << endl;
}

utilize while Circulation and cin that will do , Just type a yes int type 、s yes string type , Can continue to cycle 、 Keep typing . But if you enter a No int type , Or input s No string type ,while The loop will break .

Back to the question , The implementation code is as follows ：

int main()
{
    int a, b;
    string n;
    // Multiple sets of test data , take a Base integers n Convert to b Base number 
    while (cin >> a >> n >> b)
    {
        cout << a << " Base number ：" << n << endl;
        int ten = 0;  // Storage 10 Hexadecimal number 
        // First the a Base to zero 10 Base number 
        for (int i = 0; i <= n.size() - 1; i++)
        {
            int x = 0;  // Record this digit 
            if ('0' <= n[i] && n[i] <= '9')
            {
                x = n[i] - '0';
            }
            else if ('a' <= n[i] && n[i] <= 'z')
            {
                x = n[i] - 'a' + 10;
            }
            else if ('A' <= n[i] && n[i] <= 'Z')
            {
                x = n[i] - 'A' + 10;
            }
            ten = ten * a + x;  // This place is similar to 10 In base ten * 10 + x
        }
        cout << "10 Base number ：" << ten << endl;
        // then 10 Base to zero b Base number 
        string ans;
        while (ten > 0)
        {
            char ch;
            int x = ten % b;  // Record this digit 
            ch = x < 10 ? x + '0' : x - 10 + 'A';
            ans = ch + ans;
            ten /= b;
        }
        cout << b << " Base number ：" << ans << endl;
    }
    return 0;
}

give the result as follows ：

The results are the same as those given on the website ：

 

Swap the positions of two vectors   The notes P80