[Winter vacation practice] day1

foreword

If you accumulate steps every day, you can reach a thousand miles.

The level is limited, please correct me if there are any deficiencies.

multiple choice

1. What is the output of the following code ( )

char a=101;
int sum=200; 
a+=27;
sum+=a;
printf("%d\n",sum);

A:327

B:99

C:328

D:72


analyze

The representation range of char is -128 ~ 127.

a += 27: 101 + 27 = 128, that is, 1000 0000, the highest bit is always the sign bit, so the minimum value -128 is represented here. sum += a, which is 200 - 128, results in 72.

correct answer: D


Value range of #char

char is 1byte, 8bits integer.

Signed is the default when signed/unsigned is not specified.

unsigned char
int main()
{
    cout << UCHAR_MAX << endl;
    return 0;
}
255

All 8 bits store data, and can store 2^8 numbers, that is, 0 ~ 255

signed char
int main()
{
    cout << CHAR_MIN << endl;
    cout << CHAR_MAX << endl;
    return 0;
}
-128
127

The highest bit is the sign bit, and 7 bits store data, which can also store 2^8 numbers.

Logically speaking, the value range is -127 ~ 127 (2^7=128), how is it -128 ~ 127?

Let's look at -127 ~ 127 first, so that both +0 and "-0" are counted.

But it means "-0" is meaningless.

  • "-0"
    • Original code: 1000 0000
    • Inverse code: 1111 1111
    • Complement: 1 0000 0000
    • Truncated complement: 0000 0000

After -0 is stored in the memory, it still represents a zero value, so what is the use of it?

And -128 is different

  • -128
    • Original code: 1 ... 1000 0000
    • Inverse code: 1 ... 0111 1111
    • Complement: 1 ... 1000 0000
    • Truncated original code: 1000 0000
    • Truncated one's complement: 0111 1111
    • Truncated complement: 1000 0000

-128 is 1000 0000 after truncation, not only its own value is the "minimum value" compared to other numbers that can be represented by char, but its complement sign bit after truncation is 1, and the other bits are all 0, which can also represent "" minimum value". Therefore, the big guys put -128 into the char after truncation instead of the useless -0.

So the real value range of signed char is -128 ~ 127.

Summarize

The reason why signed char can represent -128 is because among the 128 numbers -127 ~ -0, the number that can be represented by -0 is useless (+0 has already represented it), so find "-128 and put it in char Truncate" instead of -0, let it be the minimum value of char, and its truncated complement is exactly 1000 0000, which can also express the meaning of the minimum value well.


2. What is the output after the following code is executed ( )

int value = 1024;
char condition = *((char*)(&value));
if(condition) value += 1; condition = *((char*)(&value)); 
if(condition) value += 1; condition = *((char*)(&value)); 
printf("%d %d", value, condition);

A:1026 1

B:1025 0

C:1025 1

D:1024 0

analyze

This question mainly examines the knowledge related to pointers.

*((char*)(&value)): Forcibly convert the address of int value to char*, and the pointer determines the size of the accessed memory—only 1 byte can be accessed.

char condition = *((char*)(&value)); is to take the data of the lower eight bits of value.

1024 = 0000 0000 0000 0000 0000 0100 0000 0000, whether it is big-endian storage or little-endian storage, the lower eight bits are all 0, so directly print the values ​​of both.

Summarize

The pointer type determines the size of the accessed memory


correct answer: D


3. Assuming that on a 32-bit machine, read the code and select the result ( )

void func(char para[100]) {
		void *p = malloc(100);
		printf("%d, %d\n", sizeof(para), sizeof(p)); 
}

A:4,4

B:100,4

C:4,100

D:100,100


analyze

para is used as a one-dimensional character array formal parameter, and "dimension reduction" will occur - from a one-dimensional array to a pointer. Specific dimensionality reduction method: dimensionality reduction into the address of the first element.

Again on a 32bit machine, so sizeof(para) = 4bytes

p points to the 100 bytes opened by malloc, but the calculation in the question is p itself, not the space it points to, so sizeof(p) = 4bytes

Summarize

Array parameters will be reduced to pointers to their elements


Correct answer: A

4. The output of the following program after execution is ( )

#include <stdio.h>

void func(char *p) { p = p + 1; } 
int main()
 {
		char s[] = {'1', '2', '3', '4'}; 
  	func(s);
 		printf("%c", *s);
 		return 0;

}

A:2

B: compile error

C:1

D: not sure

analyze

Pass the address of the first element to call func, but func is not dereferenced, only the formal parameter itself is changed, and s is not affected.

So the printed result is 1.

Choose C.

Summarize

Formal parameters do not change actual parameters

5. The definition of the known array D is int D[4][8]; Now this array needs to be passed as an actual parameter to a function for processing. The following can be described as the corresponding formal parameter variables [multiple choice] ( )

A:intD[4][]

B:int*s[8]

C:int(*s)[8]

D:intD[][8]

analyze

int D[4][8] as a formal parameter, will reduce the dimension - become a pointer to its first element, that is, int (*D)[8], array pointer

A: It does not conform to the grammatical specification. For an n-dimensional array, the last n-1 [] must be specified. mistake.

B: int*s[8] is an array of pointers, which does not conform to the form of formal parameter int (*D)[8]. mistake.

C: is an array pointer, no problem

D: As it is, no problem

Summarize

Priority: [] > *

programming questions

1. automorphic number

describe

An automorphic number is a natural number whose mantissa of the square of a number is equal to the number itself. For example: 25^2 = 625, 76^2 = 5776, 9376^2 = 87909376. Request the number of automorphic numbers within n (including n)

Data range: 1≤n≤10000

Enter a description:

int integer

Output description:

The number of automorphic numbers within n.

Example 1

enter:

6

output:

4

illustrate:

There are four automorphic numbers 0, 1, 5, and 6      

train of thought

The title requires us to find the number of automorphic numbers in the range [0, n].

Automorphic number: For an n-digit number, the last n-digit number of its square is equal to this n-digit number.

How to get the last n digits of the square? Modular operation!

n % m can get the number of [0, m-1]

  • 25^2 = 625
    • %100 can get the number of [0, 99] (last 2 digits)
    • 625 % 100 = 25
  • 9376^2 = 87909376
    • %10000 can get the number of [0, 9999] (last 4 digits)
    • 87909376 % 10000 = 9376

A certain number% 10^n = can be followed by n digits.

Reference Code

#include <iostream>
using namespace std;

//Self-defense number: the last n digits of the square of n digits are equal to this n digits
bool IsSelfPreservationNum(int n)
{
    //Get the last n digits
    int base = 1, tmp = n;
    while(tmp)
    {
        base *= 10;
        tmp /= 10;
    }

    //Determine whether n and the last n digits of its square are equal
    return n == (n*n) % base;
}

int main() 
{
    //Find the number of automorphic numbers in the range [0, n]
    int n = 0, cnt = 0;
    cin >> n;

    for(int i = 0; i <= n; ++i) if(IsSelfPreservationNum(i)) ++cnt;

    cout << cnt << endl;
    
    return 0;
}

Summarize

n % m = [0, m-1]

2. counting prime numbers

Given an integer n , returns the number of all prime numbers less than a nonnegative integer n .

Example 1:

enter: n = 10
 Output: 4
 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7 . 

Example 2:

enter: n = 0
 output: 0

Example 3:

enter: n = 1
 output: 0 

hint:

  • 0 <= n <= 5 * 106

Idea 1: enumeration method

A prime number is a number that can only be divisible by 1 and itself, otherwise it is a composite number (it can be written in the form of C = A * B).

*0 and 1 are not prime numbers

For a number n, enumerate [2, n-1]. Trial division, if it can be divisible evenly, it is a composite number; if not, it is a prime number

Two optimizations...

Optimization 1:

An even number greater than 2 cannot be a prime number (it must be written as C = A * B ).

It should be noted that 2 is a prime number, we have to make up.

Optimization 2:

The idea of ​​the enumeration method is to find a composite number, if it cannot be found, it is a prime number. In order to find composite numbers, it is not necessary to traverse the entire interval.

Because proving that C is a composite number only requires C = A * B, that is, to find either A or B that can divide C. And for C = A * B, the maximum value of A or B is root C. For example, for C = 16, there are 1*16 2*8 4*4, three combinations, 4*4 is the largest case of A or B.

For C = A * B, the maximum value of A or B is the root C. Can also say A^2 < C or B^2 < C .

Reference Code

#include <iostream>
#include <algorithm>
using namespace std;

bool IsPrime(int n)
{
    //optimization 2
    for(int i = 2; i*i <= n; ++i) //i is the A or B we are looking for, i^2 < n
        if(n % i == 0) return false;

    return true;
}

int main() 
{
    int n = 0;
    cin >> n;

    int cnt = 0;
    //optimization 1
    for(int i = 3; i < n; i += 2) if(IsPrime(i)) ++cnt;
    ++cnt; //Make up the even number 2
    cout << cnt << endl;

    return 0;
}

Idea 2: Elsieve sieve

The enumeration method does not take into account the connection between numbers, so it is difficult to continue to optimize the time complexity. The next Eratosthenes sieve method, referred to as the Eratosthenes sieve, is considered.

General idea: If x is a prime number, then the multiples of x greater than x 2x, 3x,... must be composite numbers, not prime numbers.

That is,

A multiple of a prime number must not be a prime number.

Given a vector<int> isPrime(n, 1), if isPrime[i] is 1, it means it is a prime number, and if it is 0, it means it is not a prime number.

According to the meaning of the question, traverse [2,n] from small to large: if this number is a prime number, mark all multiples greater than it as composite numbers. For example, find the number of prime numbers in [2,10].

Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 1, 1, 1, 1, 1, 1,  1]

2 is a prime number, and its multiples 4 6 8 10 are marked as non-prime numbers (composite numbers)
Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 1,  0]
	 
3 is a prime number, and its multiple 6 9 is marked as a non-prime number (composite number)
Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 0,  0]

5 is a prime number, and its multiple of 10 is marked as non-prime (composite) //Only when a certain number is a prime number, its multiples are screened instead of skipping directly
 Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 0,  0]
  
7 It is a prime number, there are no multiples in the range, and it is not marked
 Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 0,  0]
 
finally isPrime There are 4 positions marked as 1, that is, there are 4 prime numbers

optimization:

After reading the examples, we can also find that it is actually redundant to sieve from 2x when sieving, and we should start sieving directly from x^2, because 2x,3x, ... these numbers have been marked by multiples of other numbers before x.

for example

2 is a prime number, and its multiples 4 6 8 10 are marked as non-prime numbers (composite numbers)
Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 1,  0]
  
3 is a prime number, and its multiple 6 9 is marked as a non-prime number (composite number)
Number to iterate over:[2, 3, 4, 5, 6, 7, 8, 9, 10]
	isPrime [1, 1, 0, 1, 0, 1, 0, 0,  0]

When sieving multiples of 3, you should not start from 2x(6), because 2x has been screened out as a multiple of 2, and you should start directly from x^2(9).

Reference Code

class Solution {
public:
    int countPrimes(int n) 
    {
        vector<int> isPrime(n, 1);
        int cnt = 0;
        for(int i = 2; i < n; ++i)
        {
            if(isPrime[i])
            {
                ++cnt;
                if((long long)i * i < n) //Numbers greater than n don't care about us
                {
                    for(int j = i * i; j < n; j += i)
                    {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return cnt;
    }
};

Summarize

Better and smarter approaches come from a stronger understanding of requirements. Where is the strength? More angles, deeper understanding.

The Esperanto sieve is to screen out more composite numbers at a time through the connection between numbers.

That's all for today's sharing

Here is Bacon's blog, looking forward to making progress with you!

See you next time~

Tags: C C++ Algorithm

Posted by LordPsyan on Wed, 25 Jan 2023 10:12:33 +0300