【C】 Drink soda and find a single dog

Blog home page : XIN-XIANG Rong
Series column :【 from 0 To 1,C Language learning 】
A short sentence : If you are in full bloom , Butterflies come ！
Blog description : Do what you can , Write every blog , Help yourself familiarize yourself with what you have learned , I also hope these contents can help some partners on the way of learning , If errors and deficiencies are found in the article , Also hope to leave a message in the comment area , We communicate progress together ！

Preface

Two basic topics for comparative training of programming thinking and logical thinking , Use C Language implementation

One . Looking for a single dog

1. Topic content ：

Only two numbers in an array appear once , All the other numbers came up twice ; Find these two numbers that only appear once .

2. Their thinking

Ideas 1：

• Violent solution , Compare each number in the array with all the numbers in the array , And record the number of times that the number in the array is equal to it , If the equal number of times is 1, That is, the number that only appears once .

Ideas 2：

• The solution to the problem of finding a number that only appears once is to find a number and XOR all the numbers in it , The XOR result of the same number is 0, So the result of exclusive or of all numbers is the result of exclusive or of only two different numbers .
• The result is definitely not 0（ Or they'll all pair up ）, So there must be at least one binary bit in it 1.
• Find out the value is 1 This one , Divide the results into two groups with the value of this bit , The value is 1 They are divided into groups , The value is 0 They are divided into groups , After grouping, these two numbers have only one separate number in their respective groups .
• Therefore, the numbers in the two groups are XOR together , You can get these two separate numbers

3. Code implementation

// Method 1 
#include<stdio.h>
int main()
{
    
	int arr[] = {
     1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,7,9,10 };
	int count = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	int j = 0;
	for (i = 0; i < sz; i++)
	{
    
		for (j = 0, count = 0; j < sz; j++)
		{
    
			if (arr[i] == arr[j])
			{
    
				count++;
			}
		}
		if (count == 1)
		{
    
			printf("%d ", arr[i]);
		}
	}
	printf("\n");
	return 0;
}


// Method 2 
#include<stdio.h>

void Find_single_num(int arr[], int sz, int* num1, int* num2)
{
    
	int i = 0;
	int ret = 0;
	// First, XOR all numbers 
	for (i = 0; i < sz; i++)
	{
    
		ret ^= arr[i];
	}
	// Find out which position of the result after XOR appears 1
	int pos = 0;
	for (pos = 0; pos < 32; pos++)
	{
    
		if (((ret >> pos) & 1) == 1)
		{
    
			break;
		}
	}
	// Group XOR 
	for (i = 0; i < sz; i++)
	{
    
		if (((arr[i] >> pos)&1) == 1)
		{
    
			*num1 ^= arr[i];
		}
		else
		{
    
			*num2 ^= arr[i];
		}
	}
}

int main()
{
    
	int arr[] = {
     1,2,3,4,5,1,2,3,4,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num1 = 0;
	int num2 = 0;
	
	Find_single_num(arr, sz, &num1, &num2);
	printf("%d %d\n", num1, num2);
	
	return 0;
}

Two . Drink soda

1. Topic content ：

Drink soda ,1 Bottle of soda 1 element ,2 An empty bottle can be exchanged for a soda , to 20 element , How much soda can I drink .

2. Their thinking

Ideas 1：

• 20 Yuan can be drunk first 20 bottle , At this time, I have 20 Empty bottles
• stay 20 On the basis of the bottle, add the soda water replaced by the empty bottle to count , Empty bottles per time /2 It's the number of convertible soda
• Two empty bottles can drink one , After drinking , Empty bottles are left ：empty/2( The bottle produced after drinking two empty bottles ) + empty%2( Not enough bottles to change )
• If the number of bottles exceeds 1 individual , You can continue to change , That is, repetition 2

Ideas 2：

• According to the above rules of drinking water and changing bottles , You can find , It's actually an arithmetic sequence ：money*2-1

3. Code implementation

// Method 1 :
#include<stdio.h>
int main()
{
    
	int money = 0;
	int total = 0;
	int empty = 0;

	scanf("%d", &money);

	total = money;
	empty = money;
	while (empty > 1)
	{
    
		total += empty / 2;
		empty = empty / 2 + empty % 2;
	}

	printf("total = %d\n", total);
	return 0;
}


// Method 2 
#include<stdio.h>
int main()
{
    
	int money = 0;
	int total = 0;
	int empty = 0;

	scanf("%d", &money);

	if (money <= 0)
	{
    
		total = 0;
	}
	else
	{
    
		total = money * 2 - 1;
	}
	printf("total = %d\n", total);


	return 0;
}

Conclusion

Dear friends , It's fate to see here , I hope my content can bring you a little help , If you can, support it for three times ！！！ Thank you for coming here , We can learn and communicate together , Progress together ！！！ come on. ！！！