Problem Solving with Algorithms and Data Structures using Python.使用Python解決演算法和資料結構的問題，

By Brad Miller and David Ranum, Luther College

Assignments

分配

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.
Gerry Jenkins在YouTube上錄制了一組精彩的視頻來支持本文的所有章節，

1.Introduction

1、簡介

1.1Objectives

1.1目的

To review the ideas of computer science, programming, and problem-solving.
復習計算機科學、編程和解決問題的思想，
To understand abstraction and the role it plays in the problem-solving process.
理解抽象和它在解決問題的程序中所扮演的角色，
To understand and implement the notion of an abstract data type.
理解和實作抽象資料型別的概念，
To review the Python programming language.
回顧Python編程語言，

1.2. Getting Started

1.2入門指南

The way we think about programming has undergone many changes in the years since the first electronic computers required patch cables and switches to convey instructions from human to machine.
自從第一代電子計算機需要接線和開關來將人的指令傳送到機器中，我們思考編程的方式在這些年里經歷了許多變化，
As is the case with many aspects of society, changes in computing technology provide computer scientists with a growing number of tools and platforms on which to practice their craft.
正如社會的許多方面一樣，計算機技術的變化為計算機科學家提供了越來越多的工具和平臺，通過使用這些工具和在這些平臺上他們可以實踐自己的技術，
Advances such as faster processors, high-speed networks, and large memory capacities have created a spiral of complexity through which computer scientists must navigate.
更快的處理器、高速的網路和更大的存盤容量等技術進步創造了一個復雜的螺旋，計算機科學家必須在其中穿行，
Throughout all of this rapid evolution, a number of basic principles have remained constant.
在計算機的整個快速發展程序中，一些基本原則始終不變，
The science of computing is concerned with using computers to solve problems.
計算科學與使用計算機解決有關問題，
You have no doubt spent considerable time learning the basics of problem-solving and hopefully feel confident in your ability to take a problem statement and develop a solution.
毫無疑問，你已經花了相當多的時間學習解決問題的基礎知識，并希望對自己的問題陳述和開發解決方案的能力有信心，
You have also learned that writing computer programs is often hard.
你也知道撰寫計算機程式通常是很困難的，
The complexity of large problems and the corresponding complexity of the solutions can tend to overshadow the fundamental ideas related to the problem-solving process.
大問題的復雜性和解決辦法的相應復雜性可能會掩蓋與解決問題程序有關的基本思想，
This chapter emphasizes two important areas for the rest of the text.
這一章為正文的其余部分強調了兩個重要方面，
First, it reviews the framework within which computer science and the study of algorithms and data structures must fit, in particular, the reasons why we need to study these topics and how understanding these topics helps us to become better problem solvers.
首先，它回顧了計算機科學和演算法和資料結構的研究必須適應的框架，特別是，為什么我們需要學習這些主題，以及理解這些主題如何幫助我們來成為更好的問題解決者，
Second, we review the Python programming language.
其次，回顧Python編程語言，
Although we cannot provide a detailed, exhaustive reference, we will give examples and explanations for the basic constructs and ideas that will occur throughout the remaining chapters.
雖然我們不能提供一個詳細的，詳盡的參考，我們將給出例子和解釋的基本結構和思想，將出現在其余章節，

1.3. What Is Computer Science?

1.3.什么是計算機科學?

Computer science is difficult to define.
計算機科學很難定義，
This is probably due to the unfortunate use of the word “computer” in the name.
這可能是由于名字中不恰當地使用了“computer”這個詞，
As you are perhaps aware, computer science is not simply the study of computers.
正如你可能意識到的，計算機科學不僅僅是對計算機的研究，
Although computers play an important supporting role as a tool in the discipline, they are just that–tools.
雖然計算機作為一種工具在學科中起著重要的輔助作用，但它們只是工具而已，

Computer science is the study of problems, problem-solving, and the solutions that come out of the problem-solving process.
計算機科學是一門研究問題、解決問題以及解決問題程序的解決方法的科學，
Given a problem, a computer scientist’s goal is to develop an algorithm, a step-by-step list of instructions for solving any instance of the problem that might arise.
給定一個問題，計算機科學家的目標是開發一種演算法，一種解決任何可能出現的問題實體的一步一步的指令串列，
Algorithms are finite processes that if followed will solve the problem.
演算法是有限的程序，如果遵循它就能解決問題，
Algorithms are solutions.
演算法就是解決方案，

Computer science can be thought of as the study of algorithms.
計算機科學可以被認為是對演算法的研究，
However, we must be careful to include the fact that some problems may not have a solution.
然而，我們必須謹慎地考慮到這樣一個事實，即有些問題可能沒有解決辦法，
Although proving this statement is beyond the scope of this text, the fact that some problems cannot be solved is important for those who study computer science.
雖然證明這一說法超出了本文的范圍，但對于學習計算機科學的人來說，有些問題無法解決這一事實是重要的，
We can fully define computer science, then, by including both types of problems and stating that computer science is the study of solutions to problems as well as the study of problems with no solutions.
我們可以完全定義計算機科學，通過包括這兩種型別的問題，并指出計算機科學是對問題的解決方案的研究，以及對沒有解決方案的問題的研究，

It is also very common to include the word computable when describing problems and solutions.
在描述問題和解決方案時，包含可計算的這個詞也是很常見的，
We say that a problem is computable if an algorithm exists for solving it.
我們說一個問題是可計算的，如果存在解決它的演算法，
An alternative definition for computer science, then, is to say that computer science is the study of problems that are and that are not computable, the study of the existence and the nonexistence of algorithms.
那么，計算機科學的另一種定義是，計算機科學是對可計算和不可計算問題的研究，即對演算法存在和不存在的研究，
In any case, you will note that the word “computer” did not come up at all.
無論如何，你會注意到“computer”這個詞根本就沒有出現，
Solutions are considered independent from the machine.
解決方案是獨立于機器的，

Computer science, as it pertains to the problem-solving process itself, is also the study of abstraction.
計算機科學，由于它與解決問題的程序本身有關，也是一門抽象學，
Abstraction allows us to view the problem and solution in such a way as to separate the so-called logical and physical perspectives.
抽象允許我們以一種分離所謂的邏輯和物理視角的方式來看待問題和解決方案，
The basic idea is familiar to us in a common example.
在一個常見的例子中，基本思想是我們所熟悉的，

Consider the automobile that you may have driven to school or work today.
考慮一下你今天開去學校或作業的汽車，
As a driver, a user of the car, you have certain interactions that take place in order to utilize the car for its intended purpose.
作為一名司機，一名汽車的使用者，為了使用汽車達到預定的目的，你需要進行一定的互動，
You get in, insert the key, start the car, shift, brake, accelerate, and steer in order to drive.
你坐進車里，插入鑰匙，發動汽車，換擋，剎車，加速，轉向，以便駕駛，
From an abstraction point of view, we can say that you are seeing the logical perspective of the automobile.
從抽象的角度來看，我們可以說你看到的是汽車的邏輯視角，
You are using the functions provided by the car designers for the purpose of transporting you from one location to another.
你正在使用汽車設計師提供的功能，以便將你從一個地點運送到另一個地點，
These functions are sometimes also referred to as the interface.
這些函式有時也稱為介面，

On the other hand, the mechanic who must repair your automobile takes a very different point of view.
另一方面，要修理你汽車的機修工卻有著很是不同的看法，
She not only knows how to drive but must know all of the details necessary to carry out all the functions that we take for granted.
她不僅知道如何駕駛，而且必須知道執行我們認為理所當然的所有功能所必需的所有細節，
She needs to understand how the engine works, how the transmission shifts gears, how temperature is controlled, and so on.
她需要了解發動機是如何作業的，變速器是如何換擋的，溫度是如何控制的，等等，
This is known as the physical perspective, the details that take place “under the hood.”
這就是所謂的物理視角，即發生在“引擎蓋下”的細節，

The same thing happens when we use computers.
同樣的事情也發生在我們使用電腦的時候，
Most people use computers to write documents, send and receive email, surf the web, play music, store images, and play games without any knowledge of the details that take place to allow those types of applications to work.
大多數人使用計算機撰寫檔案、發送和接收電子郵件、瀏覽網頁、播放音樂、存盤影像和玩游戲，而不知道這些型別的應用程式作業時所發生的細節，
They view computers from a logical or user perspective.
他們從邏輯或用戶的角度來看待計算機，
Computer scientists, programmers, technology support staff, and system administrators take a very different view of the computer.
計算機科學家、程式員、技術支持人員和系統管理員對計算機有不同的看法，
They must know the details of how operating systems work, how network protocols are configured, and how to code various scripts that control function.
他們必須知道作業系統是如何作業的細節，網路協議是如何配置的，以及如何撰寫控制功能的各種腳本，
They must be able to control the low-level details that a user simply assumes.
它們必須能夠控制用戶簡單假設的底層細節，

The common point for both of these examples is that the user of the abstraction, sometimes also called the client, does not need to know the details as long as the user is aware of the way the interface works.
這兩個例子的共同點是，抽象的用戶，有時也稱為客戶端，只要用戶知道介面的作業方式，就不需要知道細節，
This interface is the way we as users communicate with the underlying complexities of the implementation.
這個介面是我們作為用戶與實作的底層復雜性進行通信的方式，
As another example of abstraction, consider the Python math module.
作為抽象的另一個例子，考慮Python數學模塊，
Once we import the module, we can perform computations such as
匯入模塊后，就可以執行諸如此類的計算

>>> import math
>>> math.sqrt(16)
4.0
>>>

This is an example of procedural abstraction.
這是程式性抽象的一個例子，
We do not necessarily know how the square root is being calculated, but we know what the function is called and how to use it.
我們不一定知道如何計算平方根，但我們知道這個函式名以及如何使用它，
If we perform the import correctly, we can assume that the function will provide us with the correct results.
如果我們正確地執行匯入，我們可以假定函式將為我們提供正確的結果，
We know that someone implemented a solution to the square root problem but we only need to know how to use it.
我們知道有人解決了平方根問題但我們只需要知道如何使用它，
This is sometimes referred to as a “black box” view of a process.
這有時被稱為流程的“黑盒”視圖，
We simply describe the interface: the name of the function, what is needed (the parameters), and what will be returned.
我們只是簡單地描述介面:函式的名稱、需要什么(引數)以及將回傳什么，
The details are hidden inside (see Figure 1).
詳細資訊隱藏在內部(參見圖1)，

Figure 1: Procedural Abstraction
圖1:程序抽象

1.4. What Is Programming?

1.4.編程是什么?

Programming is the process of taking an algorithm and encoding it into a notation, a programming language, so that it can be executed by a computer.
編程是將一種演算法編碼成一種符號，一種編程語言，這樣它就可以被計算機執行的程序，
Although many programming languages and many different types of computers exist, the important first step is the need to have the solution.
盡管存在許多編程語言和許多不同型別的計算機，但重要的第一步是需要有解決方案，
Without an algorithm there can be no program.
沒有演算法就沒有程式，

Computer science is not the study of programming.
計算機科學不是關于編程的研究，
Programming, however, is an important part of what a computer scientist does.
然而，編程是計算機科學家作業的一個重要部分，
Programming is often the way that we create a representation for our solutions.
編程通常是我們為解決方案創建表示的方式，
Therefore, this language representation and the process of creating it becomes a fundamental part of the discipline.
因此，這種語言表征及其創造程序成為該學科的一個基本組成部分，

Algorithms describe the solution to a problem in terms of the data needed to represent the problem instance and the set of steps necessary to produce the intended result.
演算法根據表示問題實體所需的資料以及產生預期結果所需的步驟集來描述問題的解決方案，
Programming languages must provide a notational way to represent both the process and the data.
編程語言必須提供一種符號方式來表示程序和資料，
To this end, languages provide control constructs and data types.
為此，語言提供了控制結構和資料型別，

Control constructs allow algorithmic steps to be represented in a convenient yet unambiguous way.
控制結構允許以一種方便而明確的方式表示演算法步驟，
At a minimum, algorithms require constructs that perform sequential processing, selection for decision-making, and iteration for repetitive control.
至少，演算法需要執行順序處理、決策選擇和重復控制迭代的構造，
As long as the language provides these basic statements, it can be used for algorithm representation.
只要語言提供了這些基本陳述句，它就可以用于演算法表示，

All data items in the computer are represented as strings of binary digits.
計算機中的所有資料項都用二進制數字串表示，
In order to give these strings meaning, we need to have data types.
為了賦予這些字串意義，我們需要資料型別，
Data types provide an interpretation for this binary data so that we can think about the data in terms that make sense with respect to the problem being solved.
資料型別為這個二進制資料提供了一種解釋，這樣我們就可以根據要解決的問題來考慮資料，
These low-level, built-in data types (sometimes called the primitive data types) provide the building blocks for algorithm development.
這些低級的內置資料型別(有時稱為原始資料型別)為演算法開發提供了構建塊，

For example, most programming languages provide a data type for integers.
例如，大多數編程語言都提供整數的資料型別，
Strings of binary digits in the computer’s memory can be interpreted as integers and given the typical meanings that we commonly associate with integers (e.g. 23, 654, and -19).
計算機記憶體中的二進制數字串可以被解釋為整數，并給出我們通常與整數相聯系的典型含義(例如23,654和-19)，
In addition, a data type also provides a description of the operations that the data items can participate in.
此外，資料型別還提供了資料項可以參與的操作的描述，
With integers, operations such as addition, subtraction, and multiplication are common.
對于整數，加法、減法和乘法等操作是常見的，
We have come to expect that numeric types of data can participate in these arithmetic operations.
我們期望數字型別的資料可以參與這些算術運算，

The difficulty that often arises for us is the fact that problems and their solutions are very complex.
我們經常遇到的困難是，問題及其解決辦法是非常復雜的，
These simple, language-provided constructs and data types, although certainly sufficient to represent complex solutions, are typically at a disadvantage as we work through the problem-solving process.
這些簡單的、由語言提供的結構和資料型別，雖然對于表示復雜的解決方案來說當然足夠了，但在我們解決問題的程序中，它們通常處于不利地位，
We need ways to control this complexity and assist with the creation of solutions.
我們需要控制這種復雜性的方法，并協助創造解決方案，

2020.12.22今天暫且就到這吧…