• Không có kết quả nào được tìm thấy

Computer Science One

N/A
N/A
Nguyễn Gia Hào

Academic year: 2023

Chia sẻ "Computer Science One"

Copied!
647
0
0

Loading.... (view fulltext now)

Văn bản

Although they have textbooks for various disciplines, computer science is not one of them (currently it is). Another inspiration for the structure of this book is the Computer Science I Honors course I developed.

Introduction

  • Problem Solving
  • Computing Basics
  • Basic Program Structure
  • Syntax Rules & Pseudocode
  • Documentation, Comments, and Coding Style

Software is usually written in a high-level programming language such as C or Java and then converted into machine code that can be executed by the processor. Errors such as unclosed comments or curly braces can be immediately apparent in such editors.

Table 1.1.: Various units of digital information with respect to bytes. Memory is usually measured using powers of two.
Table 1.1.: Various units of digital information with respect to bytes. Memory is usually measured using powers of two.

Basics

Control Flow

  • Flowcharts

Control nodes are automated steps, while action nodes are steps that are performed as part of the algorithm being mapped. We will further distinguish between two types of processes using two different colors: We use green to represent boxes that are steps directly related to the algorithm being depicted.

Variables

  • Naming Rules & Conventions
  • Types
  • Declaring Variables: Dynamic vs. Static Typing
  • Scoping

For example, most programming languages ​​do not allow spaces (space, tab, etc.) in a variable identifier. For example, to convert between uppercase and lowercase you just need to "flip" the second bit (0 for uppercase, 1 for lowercase).

Figure 2.2.: Example of a flowchart for a simple ATM process
Figure 2.2.: Example of a flowchart for a simple ATM process

Operators

  • Assignment Operators
  • Numerical Operators
  • String Concatenation
  • Order of Precedence
  • Common Numerical Errors
  • Other Operators

An assignment operator is different: it means assign the value on the right-hand side to the variable on the left-hand side. The value stored in variable a at the time this statement is executed is copied to variable b. The right-hand side can also be a more complex expression, for example the result of adding two numbers together.

For example, when you add a very large number a and a very small number b, the result may not be different from the value of a.

Basic Input/Output

  • Standard Input & Output
  • Graphical User Interfaces
  • Output Using printf() -style Formatting
  • Command Line Input

Languages ​​support formatting directly to standard output and also to strings that can be further used or manipulated. Remember that in many languages ​​you can concatenate a string and a non-string type to produce a string that can then be output to standard output. The ideas date back to the mid-1960s, but the modern printf() comes from the C programming language.

Most support either printing the resulting formatted output to standard output as well as to strings and other output mechanisms (files, streams, etc.).

Table 2.5.: printf() -style Methods in Several Languages. Languages support format- format-ting directly to the Standard Output as well as to strings that can be further used or manipulated
Table 2.5.: printf() -style Methods in Several Languages. Languages support format- format-ting directly to the Standard Output as well as to strings that can be further used or manipulated

Debugging

  • Types of Errors
  • Strategies

This is input provided at the command line when the program is executed. However, this does not mean that the program is completely free of errors, only that it is free of the types of errors (syntax errors) that the compiler can detect. Rigorous testing can be as complex (or even more complex) than writing the program itself.

However, the more test cases we design and execute, the more confident we are that the program is correct.

Examples

  • Temperature Conversion
  • Quadratic Roots

Exercises

Write a program that prompts the user for a radius r and outputs the surface area and volume of the corresponding sphere. Write a program that prompts the user for a velocity representing the percentage p of the speed of light (that is, p= vc) and a duration in hours and outputs the relative duration on Earth. Write a program that prompts the user for an amount m (mass, in kilograms) of an isotope and its half-life H as well as a number of years y and outputs the amount of the isotope remaining after y years.

Exercises Write a program that asks the user to enter D, D0, N and t1/2 and calculates the estimated age of the material, t.

Figure 2.4.: Intersection of two circles.
Figure 2.4.: Intersection of two circles.

Conditionals

Logical Operators

  • Comparison Operators
  • Negation
  • Logical And
  • Logical Or
  • Compound Statements
  • Short Circuiting

The negation operator is an operator that "flips" the truth value of the expression to which it is applied. If one of its operands is false, or if both of them are false, then the result of the logical AND is false. A statement that is always false regardless of the truth values ​​of its variables is a contradiction.

The answer is no: since a is false regardless of the truth value of b, the statement is false because logically And.

Table 3.1.: Comparison Operators
Table 3.1.: Comparison Operators

The If Statement

The logical statement attached to the if statement immediately follows the "if" keyword and is usually surrounded by parentheses. As in the flowchart, if hconditioni evaluates to true, the block of code bound to the statement is executed in its entirety. Otherwise, if the condition evaluates to false, the code block bound to the statement is skipped in its entirety.

A simple if statement can be seen as a "do this if and only if condition holds".

The If-Else Statement

Alternatively, "if this condition holds, do this, otherwise don't." In both cases, once the if statement has finished executing, the program returns to its normal sequential control flow. In an if statement, the normal flow of control is interrupted and a block of code is executed only if the given condition is true, otherwise not. In fact, the if statement is just an if-else statement with the else block omitted (similarly, we could have defined an empty else block, but since it would have no effect, a simple if statement without else block preference).

As with an if statement, both the code block associated with the if statement and the code block associated with the else statement are executed in full or not at all.

Figure 3.1.: Control flow diagrams for sequential control flow and an if-statement. In sequential control, statements are executed one after the other as they are written
Figure 3.1.: Control flow diagrams for sequential control flow and an if-statement. In sequential control, statements are executed one after the other as they are written

The If-Else-If Statement

Each of the code blocks in an if-else-if control structure is mutually exclusive. You can generalize an if-else-if statement to specify as many conditions as you like. The design of if-else-if statements must be done carefully to ensure that your statements are mutually exclusive and capture the logic you intend.

However, it is unnecessary to do this if we order our conditions appropriately and we can possibly write simpler conditions if we remember the fact that the if-else-if statement is mutually exclusive.

Figure 3.3.: Control Flow for an If-Else-If Statement. Each condition is evaluated in sequence
Figure 3.3.: Control Flow for an If-Else-If Statement. Each condition is evaluated in sequence

Ternary If-Else Operator

Examples

  • Meal Discount
  • Look Before You Leap
  • Comparing Elements
  • Life & Taxes

Alternatively, we can use an if-else statement to perform alternative operations or handle the situation differently. If the last names are equal, then we will want to order them by their first names (Jane before John). If both their first and last names are the same, we'll say that either order is fine.

We can then calculate the amount of a tax credit and adjust the tax accordingly using similar if-else-if and if-else statements as in Algorithm 3.10.

Table 3.6.: 2014 Tax Brackets for Married Couples Filing Jointly
Table 3.6.: 2014 Tax Brackets for Married Couples Filing Jointly

Exercises

Write a program that prompts the user for the observed boiling point of a substance in degrees Celsius and identifies the substance if the observed boiling point is within 5% of the expected boiling point. If the data entry is more than 5% higher or lower than any of the boiling points in the table, it should yield an unknown substance. Also note that if the cut is short enough, the remaining tile can be used at the other end of the room (the same goes for corners).

In this case, we lay the tiles from the center of the room (8 whole tiles), but are left with 0.9 on each side.

Table 3.7.: Expected Boiling Points
Table 3.7.: Expected Boiling Points

Loops

While Loops

  • Example

Finally, the loop statement is usually executed at the end of the loop within the block of code associated with the loop. The code returns to the top of the loop and again evaluates the continuation condition (which is still true as i= 2≤10). On the 10th iteration of the for=10 loop, the loop will execute for the last time.

The loop still loops back up and the continuation condition is checked one last time.

For Loops

  • Example

As a more concrete example, consider Algorithm 4.5 in which we do the same iteration (I will assume the values, but in each iteration we add the value of i for that iteration to a running total, sum. On the first iteration of the loop , i= 1 and sosum will be given the value sum+i at the end of the loop, i will be incremented and will have a value of 2. The continuation condition is still satisfied, so again the loop body executes and sum will be the value sum+ is given i= 1 + 2 = 3.

The continuation condition is still checked, but since 116≤10, the loop body will not be executed and the loop will terminate, resulting in a final sum value of 55.

Do-While Loops

Do-while loops are typically used in scenarios where the first iteration is used for "setup". A common example is when the loop body performs an operation that can result in an error code (or flag) that is either true (an error occurred) or false (no error occurred). From this point of view, the do-while loop can also be seen as a do-until loop: execute a task until some condition is no longer met.

Figure 4.2.: A Do-While Loop Flow Chart. The continuation condition is checked after the loop body.
Figure 4.2.: A Do-While Loop Flow Chart. The continuation condition is checked after the loop body.

Foreach Loops

Other Issues

  • Nested Loops
  • Infinite Loops
  • Common Errors
  • Equivalency of Loops

Most of the time, an infinite loop is not something you want and usually you need to externally terminate (sometimes referred to as "killing") your buggy program. This can be considered an infinite loop, as it has no termination condition. In this example, the while loop binds to an empty executable statement and results in an infinite loop.

A failure to properly increment a counter can lead to incorrect results or even an infinite loop.

Problem Solving With Loops

It may not seem obvious at first, but in fact any type of loop can be rewritten as any other type of loop and perform equivalent operations. For example, we could design a language where every loop must be a while loop, but there are situations where it would be more "natural" to write code with a for loop. By providing different options, programmers can choose what type of loop to write.

In general, there are no "rules" about which loop should be applied to which situation.

Examples

  • For vs While Loop
  • Primality Testing
  • Paying the Piper

A key observation is that we have already solved part of the problem: determining whether a given number is prime in the previous exercise. To start, we will need to calculate the monthly payment using the formula above and for that we will need a monthly interest rate. The balance will be updated month-to-month, so we'll use another variable to represent the balance.

Using the ourmonth variable, we'll start by initializing it to 1 and loop through the last month, n.

Exercises

Write a program that takes n as input and gives an approximation of π according to the series above. Write a program that will print numbers 1 to n where n is provided as a command line argument. Write a program that takes a list of number pairs representing latitude/longitude (on the scale, negative values ​​correspond to the southern and western hemispheres).

Write a program that takes a string as command line input (which may contain spaces) and calculates its entropy.

Figure 4.3.: Plot of f (x) = sin x x
Figure 4.3.: Plot of f (x) = sin x x

Functions

  • Defining & Using Functions
    • Function Signatures
    • Calling Functions
    • Organizing
  • How Functions Work
    • Call By Value
    • Call By Reference
  • Other Issues
    • Functions as Entities
    • Function Overloading
    • Variable Argument Functions
    • Optional Parameters & Default Values
  • Exercises

So, in effect, copies of variable values ​​are passed to the function. Passing variables by value means that the function is provided with copies of the values ​​stored in the variables. Passing variables by reference means that the memory address of the variables is provided to the function.

The function may only return an integer in the range 1–9 (it may only return zero if x= 0).

Figure 5.1.: A function declaration (prototype) in the C programming language with the return type, identifier, and parameter list labeled.
Figure 5.1.: A function declaration (prototype) in the C programming language with the return type, identifier, and parameter list labeled.

Error Handling

  • Error Handling
  • Error Handling Strategies
    • Defensive Programming
    • Exceptions
  • Exercises
  • Basic Usage
  • Static & Dynamic Memory
    • Dynamic Memory
    • Shallow vs. Deep Copies
  • Multidimensional Arrays

The first element with index 0 is 4×0 = 0 bytes from the beginning of the array (that is, the first element is at the beginning of the array). It would be inappropriate to return static fields from a function, since the field is part of the stack frame, which is destroyed when the function returns control back to the calling function (discussed in more detail below). The system responds by allocating a portion of heap memory, which the program can then use to store items in the array.

If the memory is no longer referenced, it is "garbage" and becomes eligible to be "collected". The system itself then frees the memory and makes it available to the program or operating system.

Figure 7.1.: An integer array of size 10. Using zero-indexing, the first element is at index 0, the last at index 9.
Figure 7.1.: An integer array of size 10. Using zero-indexing, the first element is at index 0, the last at index 9.

Hình ảnh

Table 1.1.: Various units of digital information with respect to bytes. Memory is usually measured using powers of two.
Figure 1.1.: Depiction of Computer Memory. Each address refers to a byte, but different types of data (integers, floating-point numbers, characters) may require different amounts of memory
Figure 1.2.: A Compiling Process
Figure 2.1.: Types of Flowchart Nodes. Control and action nodes are distinguished by color
+7

Tài liệu tham khảo