Introduction to Computing and Fundamentals of Programming Review Guide

Pre-view Tips#

None of the code in this article is guaranteed to be reliable. It is only an example for easy understanding. If there are any problems, I am not responsible, and I welcome everyone to point them out.

Introduction#

This article provides a simple overview of the knowledge in Introduction to Computing.

Computer Programming Languages#

Definition: A language used to write computer programs, expressing and describing the data to be processed and the steps and processes for solving problems. It is a whole composed of strings consisting of characters from a finite alphabet according to predefined rules (syntax).

Computing Models#

Turing Machine
1. Components
  1. An infinite tape
  2. A read/write head
  3. Internal states
  4. A program for controlling this box
2. Principle
  1. Read and write the tape, move according to the program's commands and its internal state until the final result is obtained.
Automaton (Finite State Automaton)
1. Components
  1. A finite state controller
  2. A read head
  3. An input tape with characters written on it
2. Working Principle
  1. The read head moves from left to right on the input tape. Whenever the read head reads a character from the tape, it causes a change in the controller's state and moves the read head one symbol to the right.
3. State Transition Diagram
  1. Node: Represents a state
  2. Edge: Represents a transition relationship

C Language (Important)#

Syntax#

1. Definition#

Variable Definition
Common variables in C include the following:

int a;
long long b;
char c;
float b;
double e;

Function Definition

return_type function_name( parameter list )
{
   body of the function
}

Array Definition

One-dimensional array

type arrayName[arraysize];

Multidimensional array

type arrayName[arraysize1][..]..[..][arraysizen];

Pointer Definition

type *var-name;

type is the type to which var-name points

2. Input and Output#

Input

int scanf(const char *format, ...);
char *gets(char *s);
char getchar(void);

scanf() is used for formatted input,
gets() can read a whole line of characters,
getcchar() can read a single character

Output

int printf(const char *format, ...);
int puts(const char *s);
int putchar(int c);

Similar to the above
printf() is used for formatted output,
puts() can output a string,
putchar() can output a single character

Format Specifiers

Character	Description
`d`	Signed decimal integer
`u`	Unsigned decimal integer
`f`	Double in decimal notation
`s`	String of characters
`c`	Single character

Modifiers

Character	Description
`l`	For integer types, indicates a long-sized integer parameter. For floating-point types, indicates a double-sized integer parameter.
`ll`	For integer types, indicates a long long-sized integer parameter.

For more information, refer to printf format string

Flow Control#

Conditional Statements

if (...) {

} else {

}

There can be no else or multiple nested if statements.

switch

switch(...) {
    case ..:
        do some thing
        break;
    case ..:
        do some thing
        break;
    /* The number of cases is arbitrary */
    default: /* Optional */
        do some thing
}

Loops

while

while(condition)
{

}

for ( init; condition; increment ) {

}

do...while

do
{

}while( condition );

Operators#

Arithmetic Operators +-*/%
Relational Operators ==,!=,>,<,>=,<=
Logical Operators &&,||,!

Structures#

struct struct_name {
    type val_name_1;
    ...
    type val_name_n;
} s1;

struct struct_name s2;

typedef struct {
    type val_name_1;
    ...
    type val_name_n;
}struct_name; 

truct_name s1, s2;

A structure can be understood as combining multiple variables into one variable.
After defining a structure, we have constructed a new variable type.
We can use this variable type to define variables.
To access variables in a structure, we need to use the . operator.

Pointers#

Pointers to Variables
A pointer variable stores the address of another variable.
For example:

int a;
int *p = &a;

In this case, the variable p stores the address of a.
We can access a variable
either directly by its variable name
or indirectly by using its address to access its value.

Pointers to Pointers
We know that pointers are also a type of variable.
So we can also define a pointer to a pointer, like int **p.
We can understand it as p points to another pointer, and that pointer points to a variable.
We can directly treat the value after dereferencing a pointer as a complete variable.
In other words, we can treat *p as a whole and it is equivalent to the variable name it points to in a sense.
Pointers to Functions

return_type (*function_name)( parameter list );

Please note that the first parentheses cannot be omitted, otherwise it will become a function that returns a pointer.
A function pointer can point to a function, where the parameter names in the parameter list can be omitted, but the parameter types cannot be omitted. It is similar to function declaration.

Pointers to Structures
Pointers to structures are similar to pointers to variables.
The problem is that the . operator has a higher precedence than the * operator, so if we want to access an element, (*a).b must be enclosed in parentheses.
To simplify this, we have a new operator ->, which makes (*a).b equivalent to a->b, which is more concise and easier to understand.

Function Parameters and Return Values#

Parameters are passed by value, and the parameters in the function do not affect the original values.
If you want to modify the original values, the value passed in must be the address of the value to be modified.
When passing an array as a function parameter, only the size of the first dimension can be omitted, and the sizes of other dimensions must correspond when passing the parameter. The elements in the array can be modified.
A function cannot return an array.

Strings#

In C language, a string is simply a character array.
The end of a string is '\0', corresponding to ASCII code 0.
The string.h library contains many commonly used functions for strings, such as strlen(), strcpy().
I won't go into detail here, you can search for related content online.

Algorithms#

1. Swapping the Values of Two Variables#

Suppose we have two variables a and b, and we want to swap them.

int temp = a;
a = b;
b = temp;

2. Sorting Algorithms#

Let's focus on bubble sort.
In each iteration of bubble sort, the kth largest (or kth smallest) number is moved to the kth position.
After n-1 rounds, we can obtain a sorted array.

Let a[i] be the array to be sorted.

for (int i = 1; i < n; i++) {
    for (int j = 1; j <= n - i; j++) {
        if (a[j] > a[j + 1]) {
            int temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
        }
    }
}

3. Binary Search#

Let's first consider the simplest binary search.
Suppose we have an array a[i] of length n that is already sorted in ascending order.
We want to know if a number x appears in a[i].
In this case, we can use binary search to find this number.

int l = 0, r = n, ans = n + 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] == x) {
        ans = mid;
        break;
    }
    if (a[mid] < x) l = mid + 1;
    else (a[mid] > x) r = mid - 1;
}

The final value of ans is the position of x, and if it is not found, ans is n + 1.

Another type of binary search is binary search for answers.
Binary search for answers means that we binary search the value of the answer to a problem.
By logical judgment, we can determine whether our true answer is greater or smaller than the value we divide, and then modify the values of l and r.
The condition for binary search for answers is that the answer to our problem has monotonicity.
For example, if a is feasible, then anything larger than a is definitely not feasible, and if a is not feasible, then anything smaller than a is definitely not feasible.
In this way, we can perform binary search.

Conclusion#

Due to limited space, I couldn't write the details of many contents and omitted some of them. Many contents still need to be reviewed by everyone.
I hope everyone can review seriously and wish you all good grades in the final exam.

The grades in Introduction to Computing are mostly based on accumulated knowledge in daily life. You need to write more code and solve more problems on online judges. When the amount of code reaches a certain level, quantitative changes will lead to qualitative changes, and you will have a whole new understanding of programming.