All posts by Phuc Nguyen

Reading books will never be obsolete

Books have always played an integral part in my journey growing up. While there are many different platforms of entertainment and to gain knowledge, and I do enjoy them, books will never be obsolete.

When we were little, colorful books helped us recognize the world, and they planted the seed of imagination and creativity. I will never forget my mom reading those books to me, and at the same time, explaining moral stories that came within. Children are like plain sheets of paper, and books like these are the brightest colors.

Next up, comics. I guess you have once asked your mom to get a new one every week. Or the little novels to long ones, the hesitation to read them because of the walls of text quickly faded as you read more and more.

There are two subjects that I think the learn-by-heart fashion is not suitable: 3D geometry and literature. Geometry is present everywhere in the world around us, and literature is all the reasons I mentioned above. You may argue with the high school approach of literature as one-sided, and while unfortunately that is true at the moment, literature is more than that. If you learn it by heart, then humanity could just print one massive book and distribute it to everyone. Yet you see, there are millions if not more books ready for us to read and feel, and people are still publishing new ideas in books.

Lastly, you don’t read a book once. Some books deserve more than one read. There are books that you perceive one way in the past, and differently now, maybe more differently in the future. They mark our progress as a human being. A poor man’s time machine that. Maybe you’ll read your favorite novel, and the image of a 7-year-old you enjoying the same thing more than 10 years ago pops up. Personally, that’s how I keep my memory fresh, how I relive my childhood. Life is cruel sometimes, and the memory train with books as carriages is a good way to soften things a bit.

So read.

Kiểm tra số chẵn, số lẻ bằng phép thao tác bit trên c++

Với một người không rành máy móc thì hẳn họ cũng sẽ biết rằng máy tính hoạt động theo nguyên tắc của hệ nhị phân (0 và 1). Các phép thao tác bit (bit-wise operations) trong C++ là một thứ khá hay ho để ta có thể vận dụng hệ nhị phân để giải quyết một số bài toán lập trình, mà chủ đề hôm nay sẽ là về kiểm tra tính chẵn lẻ của một số bất kỳ.

Thuật toán kiểm tra cơ bản rất dễ hiểu. Ta thử xem liệu số n nào đó có chia hết cho 2 hay không: nếu chia hết thì số đó là số chẵn, ngược lại là số lẻ.

Với các thao tác bit, ta sẽ ghép n với số 1 bằng toán tử AND. Toán tử AND sẽ chỉ trả về 1 nếu cả hai bit đầu vào đều là 1, đúng theo bảng chân trị của lý thuyết toán rời rạc. Khi một số lẻ ở hệ thập phân được chuyển đổi sang hệ nhị phân, chữ số cuối cùng sẽ luôn là số 1. Lợi dụng điều này, ta sẽ biết được số n ban đầu là lẻ hay chẵn bằng cách xem xét output của AND.

Ưu điểm của thao tác bit là nó chạy nhanh hơn cách thông thường, với lại làm bạn ngầu hơn với cả những người đã biết lập trình (haha).

Sau đây là đoạn code C++ mô phỏng lại những gì mình vừa nói.

#include <bits/stdc++.h>
using namespace std;
int main(){
     int n = 7;
     if (n & 1){
           cout << "odd number.";
     } //& là ký hiệu của phép AND trên C++.
     else cout << "even number.";
}

Một bài lập trình hay về số nguyên tố

Số nguyên tố là thứ quá đỗi quen thuộc với những ai học toán, cũng như đối với các lập trình viên. Ai học giải thuật đều đã giải qua những bài về số nguyên tố, với độ khó dàn trải từ đơn giản tới phức tạp, từ vòng lặp thử tính chia hết tới sàng số nguyên tố Eratosthene…

Hôm nay mình rảnh thì có nghĩ ra một bài như thế này, các bạn xem qua nhé!

Đề bài: Cho hai số nguyên dương x và y (các test case đưa vào luôn đảm bảo x > y). Viết chương trình kiểm tra xem x2 – y2 có phải là số nguyên tố hay không.

Thoạt nhìn qua thì bài này khá đơn giản. Tính x2 – y2, rồi kiểm tra. Nhưng khi x và y lớn, ví dụ cỡ 1018 thì cách này sẽ chạy quá thời gian.

Hãy quan sát biểu thức x2 – y2. Nếu bạn đã học 7 hằng đẳng thức đáng nhớ, sẽ dễ thấy rằng x2 – y2 có thể được viết dưới dạng (x-y)(x+y). Vì x và y đều là các số nguyên dương, nên x 1 và y 1. Từ đó suy ra: (x+y) 1.

Xét biểu thức còn lại, x-y. Sẽ xảy ra hai trường hợp là (x-y) 1 và (x-y)=1. Với trường hợp đầu tiên, x2 – y2 sẽ không là số nguyên tố vì vi phạm định nghĩa (chỉ có hai ước là 1 và chính nó). Do đó với (x-y)=1, biểu thức ban đầu sẽ tương đương với chỉ x+y. Ta chỉ cần xét x+y là đủ. Sau đây là code miêu tả bài toán này.

bool primeSquare(long long a, long long b)
{
    if (a-b != 1) return false;
    long long num = a + b;
    if (num % 2 == 0) return false;
    for (long long i = 3; i*i <= num; i += 2)
    {
        if (num % i == 0) return false;
    }
    return true;
}

Intuitive explanation to how dividing by 0 is impossible

We all know a random number times 0 always ends up 0, but the division for 0 is impossible. Computer programs return numerous errors upon stumbling across this matter, math leaners try their best with conditions to avoid dividing by 0. Some guys on YouTube even tried to prove that 1 equals to 0 using this very infamous numerical expression.

But why is that? Let us take a very straightforward and intuitive example to explain why dividing by 0 is a meaningless act.

Say you have a delicious cake. Rashford and Pogba come to your house to eat it with you. In order to make everyone happy, the cake must be divided into 3 equal parts, so each one of you will have a third of that cake. In another scenario, it is the same cake, but you celebrate something alone and want to eat the whole thing. Simple. You divide the cake by 1, so it ends up being itself. Bon appetit!

But what happens when you attempt to divide the cake by 0? The cake just disappears. Just a second ago, a delicious piece of culinary art stays in front of you, but now it is in the void. The act itself gets ridiculous when you think about it. Where is the cake? Ask the divisor.

That is the answer for dividing by 0. You cannot destroy matters, because the act of dividing by 0 “destroys” matters and numbers. For those who studied physics, you must be familiar with the Conservation of mass: “mass can neither be created nor destroyed, although it may be rearranged in space, or the entities associated with it may be changed in form.”

Sort by moving elements to start or end with fewest moves

Getting started

You may be familiar with quick-sort, but when you stumble across this problem, it turns out to be a lot more complex. Since you need to determine the method that involves the fewest moves possible, you will have to take another approach. The given problem can be re-stated into this problem:

Problem statement

Hien is the class monitor and he wants his classmates to form a line, in which the height of every students is in ascending order. He needs to form that line by moving his classmates from the line to the start or end of it and it has to be a quick process, since Hien is very lazy and needs to play Age Of Empires right away. Write an algorithm to help him.

Input format

First line: n.

Second line: numbers indicating the height of every student in the class, each seperated by a space.

Constraints

n ≤ 100; H[i] ≤ 100000 (H[i] is the height of an individual).

Output format

An integer indicating the fewest moves possible.

Sample input

4

2 1 3 5

Sample output

1

Explanation

The student with height 1 is moved to the start of the line.

Let’s not pay attention to the ‘fewest moves’ for a while. Normally, when you see these types of ‘moving’ elements to start or end of an array, you can take a look at a basic approach.

Let’s take the Sample input as an example. With the basic approach, we search for the smallest element in the array, which is now 1. After that, we move it to the far right of the array. Then, we search for the next smallest element, which is 2, and we keep doing it until 5 is moved to the far right of the array. We come to the conclusion that for this approach, the number of moves that are taken is exactly equal to the number of elements present in the array itself. But let’s have a closer look. We can see that 2, 3 and 5 are contiguous, meaning that the relative order between them is not changed at all when sorting is completed. So, we can know that in the required algorithm, we need to conserve the order of contiguous integers. That is when std::pair comes to use.

Basic approach illustration

What is std::pair, exactly?

Std::pair is a pre-defined class in C++. A pair element is consisted of 2 other sub-elements, which can be classified as first and second. In the algorithm we are searching for, as stated earlier, we can utilise std::pair to get the job done by assigning the input elements to first and its index to second.

Get the job done

After that, quick-sort comes in handy. We then use it to sort the array in ascending order. Because std::pair is used, when sorting the elements, each index is carried along with the data. Then, we can just compare the indexes of every subsequent element. Job done!

Final approach illustration

Source code (C++)