Hỏi Đáp Bao nhiêu

Có bao nhiêu số nguyên dương n gồm 3 chữ số có nghĩa

Làm quen cách viết các chương trình đơn giản, cách sử dụng:

CÂU ĐIỀU KIỆN IF
VÒNG LẶP WHILE
Phương pháp đếm
Phương pháp đệ quy

Mô tả bài toán

Cho số n, đếm số lượng chữ số của số nguyên dương n.

Ví dụ:

Hướng dẫn

Định nghĩa

Đệ quy [Recursion] là một trong những giải thuật khá quen thuộc trong lập trình [trong toán học thường được gọi với tên khác là “quy nạp”].

Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.

Ví dụ:

int Recusion[] { Recusion[]; }

Hàm đệ quy gồm 2 phần:

Phần cơ sở: Điều kiện thoát khỏi đệ quy
Phần đệ quy: Thân hàm có chứa lời gọi đệ quy

Thuật toán

Có thể giải theo 2 cách:

Dùng vòng lặp
Dùng đệ quy

Bài tập mang tính tham khảo, hỗ trợ các bạn làm quen và luyện tập với các bàn toán lập trình cơ bản trong C++.

Kteam khuyến khích các bạn tự phân tích đề bài > tự giải bài toán > debug để kiểm tra kết quả và fix lỗi trong quá trình giải. Sau đó, bạn có thể tham khảo source code mẫu để hoàn chỉnh bài tập.

Để được hỗ trợ tốt nhất, bạn có thể đặt câu hỏi ở phần bình luận bên dưới bài viết hoặc ở mục Hỏi & Đáp.

Source code tham khảo

Header.h

// Header.h #ifndef _HEADER_ #define _HEADER_ int demSoChuSo[int]; int demSoChuSoDeQuy[int]; #endif // _HEADER_

Source.cpp

// Source.cpp #include #include "Header.h" using namespace std; int main[] { int nInput; cout > nInput; int nResult = demSoChuSoDeQuy[nInput]; cout 0\}=\mathbb {Z} ^{+}}

${ 0 , 1 , 2 , … } = { x ∈ Z : x ≥ 0 } = Z 0 + {\displaystyle \{0,1,2,\dots \}=\{x\in \mathbb {Z} :x\geq 0\}=\mathbb {Z} _{0}^{+}}$

Cho tập hợp $N {\displaystyle \mathbb {N} }$ của các số tự nhiên và hàm kế thừa $S : N → N {\displaystyle S\colon \mathbb {N} \to \mathbb {N} }$ ánh xạ mỗi số tự nhiên cho một số tiếp theo, người ta có thể định nghĩa phép cộng các số tự nhiên một cách đệ quy bằng cách đặt $a + 0 = a$ và $a + S[b] = S[a + b]$ với mọi $a$ , $b$ . Khi đó $[ℕ, +]$ là một monoid giao hoán với phần tử đơn vị là 0. Nó là một monoid tự do trên phần tử sinh là 1. Monoid giao hoán này thỏa mãn thuộc tính hủy bỏ, vì vậy nó có thể được nhúng trong một nhóm. Nhóm nhỏ nhất chứa các số tự nhiên là các số nguyên.

Nếu 1 được xác định là $S[0]$ , thì $b + 1 = b + S[0] = S[b + 0] = S[b]$ . Có nghĩa là, $b + 1$ đơn giản là phần tử kế thừa của $b$ .

Trong lịch sử, quá trình đưa ra một định nghĩa toán học chính xác về số tự nhiên là một quá trình nhiều khó khăn. Các định đề Peano đưa ra những điều kiện tiên quyết cho một định nghĩa thành công về số tự nhiên. Một số phép xây dựng cho thấy rằng, với lý thuyết tập hợp đã biết, các mô hình của các định đề Peano chắc chắn tồn tại.

Các tiên đề Peano

Có một số tự nhiên 0.
Với mọi số tự nhiên $a$ , tồn tại một số tự nhiên liền sau, ký hiệu là $S[a]$ .
Không có số tự nhiên nào mà số liền sau của nó là 0.
Hai số tự nhiên khác nhau phải có hai số liền sau tương ứng khác nhau: nếu a ≠ b thì S[a] ≠ S[b].
Nếu có một tính chất nào đó được thỏa mãn với số 0, và chúng ta chứng minh được rằng với mọi số tự nhiên thỏa tính chất đó thì số liền sau của nó cũng thỏa tính chất đó, khi đó, tính chất đó được thỏa mãn với mọi số tự nhiên. [Định đề này đảm bảo rằng phép quy nạp toán học là đúng.]

Cần lưu ý rằng "0" ở định nghĩa trên không nhất thiết phải là số không mà chúng ta vẫn thường nói đến."0" ở đây chẳng qua là một đối tượng nào đó mà khi kết hợp với một hàm liền sau nào đó thì sẽ thỏa mãn các tiên đề Peano. Có nhiều hệ thống thỏa mãn các tiên đề này, trong đó có các số tự nhiên [bắt đầu bằng số không hay bằng số một].

Xây dựng dựa trên lý thuyết tập hợp

Phép xây dựng chuẩn

Trong lý thuyết tập hợp có một trường hợp đặc biệt của phép xây dựng von Neumann định nghĩa tập hợp số tự nhiên như sau:

Chúng ta định nghĩa

0 = { }

, tập hợp rỗng và định nghĩa

S[a] = a \cup {a}

với mọi

a

. Sau đó tập hợp số tự nhiên được định nghĩa là giao của tất cả các tập hợp chứa 0 mà là các tập đóng đối với hàm liền sau. Nếu chúng ta thừa nhận tiên đề về tính vô hạn thì sẽ chứng minh được định nghĩa này thỏa mãn các tiên đề Peano. Mỗi số tự nhiên khi đó bằng tập hợp của các số tự nhiên nhỏ hơn nó, sao cho:

$0 = { }$ ,
$1 = 0 \cup {0} = {0} = {{ }}$ ,
$2 = 1 \cup {1} = {0, 1} = {{ }, {{ }}}$ ,
$3 = 2 \cup {2} = {0, 1, 2} = {{ }, {{ }}, {{ }, {{ }}}}$ ,
$n = n-1 \cup {n-1} = {0, 1, \dots, n-1} = {{ }, {{ }}, \dots, {{ }, {{ }}, \dots}}$ , vân vân

Khi ta thấy một số tự nhiên được dùng như là một tập hợp, thì thông thường, ý nghĩa của nó như được trình bày ở trên. Theo định nghĩa đó, có đúng n phần tử [theo nghĩa thông thường] trong tập $n$ và $n \leq m$ [cũng theo nghĩa bình thường] khi và chỉ khi $n$ là một tập con của $m$ .

Cũng từ định nghĩa này, những cách hiểu khác nhau về các ký hiệu như

ℝn

[là một n-tuple hay là một ánh xạ từ

n

vào

ℝ

]] trở nên tương đương nhau.

Các phép xây dựng khác

Mặc dù phép xây dựng chuẩn thông dụng nhưng nó không phải là phép xây dựng duy nhất. Ví dụ về phép dựng của Zermalo:

có thể định nghĩa 0 = { } và

S[a] = a

, tạo ra

0 = { }
1 = {0} = {{ }}
2 = {1} = {{{ }}},...

Hay chúng ta có thể định nghĩa 0 = {{ }}

và

{{{1}}}

} tạo ra

0 = {{ }}
1 = {{ }, 0} = {{ }, {{ }}}
2 = {{ }, 0, 1},...

Có thể vẫn còn tranh cãi, nhưng nhìn chung người ta thường gán định nghĩa có tính lý thuyết tập hợp xưa nhất về số tự nhiên cho Frege và Russell. Trong định nghĩa của hai người này thì mỗi số tự nhiên n cụ thể được định nghĩa là tập hợp của tất cả các tập có $n$ phần tử.

Frege và Rusell bắt đầu bằng cách định nghĩa 0 là ${ { } } {\displaystyle \{\{\}\}}$ [rõ ràng đây là tập của tất cả các tập có 0 phần tử] và định nghĩa $σ [ A ] {\displaystyle \sigma [A]}$ [với A là một tập bất kỳ] là ${ x ∪ { y } ∣ x ∈ A ∧ y ∉ x } {\displaystyle \{x\cup \{y\}\mid x\in A\wedge y\not \in x\}}$ . Như vậy 0 sẽ là tập của tất cả các tập có 0 phần tử, $1 = σ [ 0 ] {\displaystyle 1=\sigma [0]}$ sẽ là tập của tất cả các tập có một phần tử, $2 = σ [ 1 ] {\displaystyle 2=\sigma [1]}$ sẽ là tập của tất cả các tập có 2 phần tử, và cứ thế. Sau đó, tập hợp của tất cả các số tự nhiên được định nghĩa như là phần giao của tất cả các tập có chứa 0 và là tập đóng với phép $σ {\displaystyle \sigma }$ [tức là nếu tập này chứa phần tử $n$ ] thì nó cũng phải chứa $σ [ n ] {\displaystyle \sigma [n]}$ ].

Định nghĩa này sẽ không dùng được trong những hệ thống thông thường của lý thuyết tập hợp tiên đề vì những tập được tạo ra như vậy quá lớn [nó sẽ không dùng được trong bất kỳ lý thuyết tập hợp nào với tiên đề tách - separation axiom]; nhưng định nghĩa này sẽ làm việc được trong Cơ sở Mới [New Foundations] [và trong các hệ thống tương thích với Cơ sở Mới] và trong một vài hệ thống của lý thuyết kiểu.

Trong phần còn lại của bài này, chúng ta sử dụng phép xây dựng chuẩn đã mô tả ở trên.

Các phép toán trên tập hợp các số tự nhiên có thể định nghĩa nhờ phép đệ quy như sau

Phép cộng

$a + 0 = a$
$a + S[b] = S[a + b]$

Phép cộng này khiến

[ℕ, +]

trở thành một vị nhóm giao hoán với phần tử trung lập là 0, cũng là một vị nhóm tự do với một hệ sinh nào đó. Vị nhóm thỏa tính chất khử và do đó có thể được nhúng trong một nhóm. Nhóm nhỏ nhất chứa các số tự nhiên là số nguyên.

Nếu chúng ta ký hiệu $S[0]$ là 1, khi đó $b + 1 = b + S[0] = S[b + 0] = S[b]$ ; tức là, số liền sau của $b$ chẳng qua là $b + 1$ .

Phép nhân

Tương tự như phép cộng, chúng ta định nghĩa phép nhân × như sau

$a \times 0 = 0$
$a \times S[b] = [a \times b] + a$

Phép nhân được định nghĩa như vậy khiến [N,×] trở thành một vị nhóm với phần tử trung lập là 1; một hệ sinh của vị nhóm này chính là tập hợp các số nguyên tố. Phép cộng và phép nhân thỏa tính chất phân phối:

a \times [b + c] = [a \times b] + [a \times c]

. Các tính chất mà phép cộng và phép nhân thỏa khiến tập số tự nhiên trở thành một trường hợp ví dụ của nửa vành giao hoán. Nửa vành là dạng tổng quát hóa đại số của số tự nhiên mà trong đó phép nhân không cần phải thỏa tính giao hoán.

Nếu chúng ta hiểu tập hợp số tự nhiên theo nghĩa"không có số 0"và"bắt đầu bằng số 1"thì các định nghĩa về phép + và × cũng vẫn thế, ngoại trừ sửa lại $a + 1 = S[a]$ và $a \times 1 = a$ .

Trong phần còn lại của bài này, chúng ta viết $ab$ để ám chỉ tích $a \times b$ , và chúng ta cũng sẽ thừa nhận quy định về thứ tự thực hiện các phép toán.

Quan hệ thứ tự

Chúng ta có thể định nghĩa một quan hệ thứ tự toàn phần trên tập số tự nhiên như sau:

Với hai số tự nhiên a,b, ta có

a \leq b

nếu và chỉ nếu tồn tại một số tự nhiên

c

sao cho

a + c = b

. Kiểu sắp thứ tự này cùng với các phép toán số học đã định nghĩa ở trên cho ta: Nếu

a

b

và

c

là các số tự nhiên và

a \leq b

, thì

a + c \leq b + c

và

ac \leq bc

Tập số tự nhiên còn có một tính chất quan trọng nữa là chúng là tập sắp tốt: mọi tập không rỗng của các số tự nhiên phải có một phần tử nhỏ nhất.

Phép chia có dư và tính chia hết

Cho hai số tự nhiên $a, b$ và $b \neq 0$ . Xét tập hợp M các số tự nhiên $p$ sao cho $pb \leq a$ . Tập này bị chặn nên có một phần tử lớn nhất, gọi phần tử lớn nhất của M là $q$ . Khi đó $bq \leq a$ và $b[q + 1] > a$ . Đặt $r = a - bq$ . Khi đó ta có

a = bq + r

, trong đó

0 \leq r < b

Có thể chứng minh rằng các số $q$ và $r$ là duy nhất. Số $q$ được gọi là thương hụt [hay vắn tắt là thương], số $r$ được gọi là số dư khi chia $a$ cho $b$ . Nếu $r = 0$ thì $a = bq$ . Khi đó ta nói rằng $a$ chia hết cho $b$ hay $b$ là ước của $a$ , $a$ là bội của $b$ .

Với hai hướng sử dụng như đã nêu ở phần giới thiệu, số tự nhiên trước hết được tổng quát hóa theo hai hướng sử dụng này: số thứ tự được dùng để mô tả vị trí của một phần tử trong một dãy sắp thứ tự và bản số dùng để xác định kích thước của một tập hợp nào đó.

Trong trường hợp dãy hữu hạn hay tập hợp hữu hạn, cả hai cách sử dụng này thực chất là đồng nhất với nhau.

Tập hợp số thực

N {\displaystyle \mathbb {N} }

: Tập hợp số tự nhiên

Z {\displaystyle \mathbb {Z} }

: Tập hợp số nguyên

Q {\displaystyle \mathbb {Q} }

: Tập hợp số hữu tỉ

I {\displaystyle \mathbb {I} }

R ∖ Q {\displaystyle \mathbb {R} \setminus \mathbb {Q} }

: Tập hợp số vô tỉ

R {\displaystyle \mathbb {R} }

: Tập hợp số thực

^ Mendelson [2008, tr. x]Lỗi harv: không có mục tiêu: CITEREFMendelson2008 [trợ giúp] says: "The whole fantastic hierarchy of number systems is built up by purely set-theoretic means from a few simple assumptions about natural numbers." [Preface[tr $x$ ]]
^ Bluman [2010, tr. 1]Lỗi harv: không có mục tiêu: CITEREFBluman2010 [trợ giúp]: "Numbers make up the foundation of mathematics."
^ The English translation is from Gray. In a footnote, Gray attributes the German quote to: "Weber 1891–1892, 19, quoting from a lecture of Kronecker's of 1886."[20][21]
^ "Much of the mathematical work of the twentieth century has been devoted to examining the logical foundations and structure of the subject." [Eves 1990, tr. 606]Lỗi harv: không có mục tiêu: CITEREFEves1990 [trợ giúp]

^ “Compendium of Mathematical Symbols”. Math Vault [bằng tiếng Anh]. 1 tháng 3 năm 2020. Truy cập ngày 11 tháng 8 năm 2020.
^ Weisstein, Eric W. “Natural Number”. mathworld.wolfram.com [bằng tiếng Anh]. Truy cập ngày 11 tháng 8 năm 2020.
^ “Natural Numbers”. Brilliant Math & Science Wiki [bằng tiếng Anh]. Truy cập ngày 11 tháng 8 năm 2020.
^ “ISO 80000-2:1111”. International Organization for Standardization.
^ a b Toán lớp 6 tập 1 - Nhà Xuất bản Giáo dục 2004
^ “Comprehensive List of Algebra Symbols”. Math Vault [bằng tiếng Anh]. 25 tháng 3 năm 2020. Truy cập ngày 11 tháng 8 năm 2020..
^ “natural number”. Merriam-Webster.com. Merriam-Webster. Bản gốc lưu trữ ngày 13 tháng 12 năm 2019. Truy cập ngày 4 tháng 10 năm 2014.
^ Number Systems and the Foundations of Analysis nói:"The whole fantastic hierarchy of number systems is built up by purely set-theoretic means from a few simple assumptions about natural numbers."[Preface, p. x]
^ Weisstein, Eric W., "Counting Number" từ MathWorld.
^ “Introduction”. Ishango bone. Brussels, Belgium: Royal Belgian Institute of Natural Sciences. Bản gốc lưu trữ ngày 4 tháng 3 năm 2016.
^ “Flash presentation”. Ishango bone. Royal Belgian Institute of Natural Sciences. Bản gốc lưu trữ ngày 27 tháng 5 năm 2016.
^ “The Ishango Bone, Democratic Republic of the Congo”. UNESCO's Portal to the Heritage of Astronomy. Bản gốc lưu trữ ngày 10 tháng 11 năm 2014., on permanent display at the Royal Belgian Institute of Natural Sciences, Brussels, Belgium.
^ Ifrah, Georges [2000]. The Universal History of Numbers. Wiley. ISBN 0-471-37568-3.
^ ... một tấm khắc tìm thấy ở Kish... vào khoảng năm 700 TCN, dùng ba dấu móc để ký hiệu một vị trí trống trong hệ thống ký hiệu có giá trị theo vị trí. Một số tấm khắc khác cũng được tạo ra cùng thời gian dùng một dấu móc để ký hiệu một vị trí trống. [1]
^ G.N. Becman. Số và khoa học về số [tiếng Nga]-bản dịch tiếng Việt của Nguyễn Hữu Trương và Thế Trường. Nhà Xuất bản Giáo dục 2003, trang 29
^ Mann, Charles C. [2005]. 1491: New Revelations of the Americas before Columbus. Knopf. tr. 19. ISBN 978-1-4000-4006-3. Bản gốc lưu trữ ngày 14 tháng 5 năm 2015. Truy cập ngày 3 tháng 2 năm 2015 – qua Google Books.
^ Evans, Brian [2014]. “Chapter 10. Pre-Columbian Mathematics: The Olmec, Maya, and Inca Civilizations”. The Development of Mathematics Throughout the Centuries: A brief history in a cultural context. John Wiley & Sons. ISBN 978-1-118-85397-9 – qua Google Books.
^ Deckers, Michael [25 tháng 8 năm 2003]. “Cyclus Decemnovennalis Dionysii – Nineteen year cycle of Dionysius”. Hbar.phys.msu.ru. Lưu trữ bản gốc ngày 15 tháng 1 năm 2019. Truy cập ngày 13 tháng 2 năm 2012.
^ Kline, Morris [1990] [1972]. Mathematical Thought from Ancient to Modern Times. Oxford University Press. ISBN 0-19-506135-7.
^ Gray, Jeremy [2008]. Plato's Ghost: The modernist transformation of mathematics. Princeton University Press. tr. 153. ISBN 978-1-4008-2904-0. Lưu trữ bản gốc ngày 29 tháng 3 năm 2017 – qua Google Books.
^ Weber, Heinrich L. [1891–1892]. “Kronecker”. Jahresbericht der Deutschen Mathematiker-Vereinigung [Annual report of the German Mathematicians Association]. tr. 2:5–23. [The quote is on p. 19]. Bản gốc lưu trữ ngày 9 tháng 8 năm 2018; “access to Jahresbericht der Deutschen Mathematiker-Vereinigung”. Bản gốc lưu trữ ngày 20 tháng 8 năm 2017.
^ Eves 1990Lỗi harv: không có mục tiêu: CITEREFEves1990 [trợ giúp]
^ Kirby, Laurie; Paris, Jeff [1982]. “Accessible Independence Results for Peano Arithmetic”. Bulletin of the London Mathematical Society. Wiley. 14 [4]: 285–293. doi:10.1112/blms/14.4.285. ISSN 0024-6093.
^ Bagaria, Joan [2017]. Set Theory . The Stanford Encyclopedia of Philosophy. Bản gốc lưu trữ ngày 14 tháng 3 năm 2015. Truy cập ngày 13 tháng 2 năm 2015.
^ Goldrei, Derek [1998]. “3”. Classic Set Theory: A guided independent study . Boca Raton, Fla. [u.a.]: Chapman & Hall/CRC. tr. 33. ISBN 978-0-412-60610-6.
^ Brown, Jim [1978]. “In defense of index origin 0”. ACM SIGAPL APL Quote Quad. 9 [2]: 7. doi:10.1145/586050.586053.
^ Hui, Roger. “Is index origin 0 a hindrance?”. jsoftware.com. Lưu trữ bản gốc ngày 20 tháng 10 năm 2015. Truy cập ngày 19 tháng 1 năm 2015.
^ This is common in texts about Real analysis. See, for example, Carothers [2000, tr. 3]Lỗi harv: không có mục tiêu: CITEREFCarothers2000 [trợ giúp] or Thomson, Bruckner & Bruckner [2000, tr. 2]Lỗi harv: không có mục tiêu: CITEREFThomsonBrucknerBruckner2000 [trợ giúp].
^ “Compendium of Mathematical Symbols”. Math Vault [bằng tiếng Anh]. 1 tháng 3 năm 2020. Truy cập ngày 11 tháng 8 năm 2020.
^ Weisstein, Eric W. “Natural Number”. mathworld.wolfram.com [bằng tiếng Anh]. Truy cập ngày 11 tháng 8 năm 2020.
^ “Listing of the Mathematical Notations used in the Mathematical Functions Website: Numbers, variables, and functions”. functions.wolfram.com. Truy cập ngày 27 tháng 7 năm 2020.
^ Rudin, W. [1976]. Principles of Mathematical Analysis. New York: McGraw-Hill. tr. 25. ISBN 978-0-07-054235-8.
^ “Standard number sets and intervals”. ISO 80000-2:2009. International Organization for Standardization. tr. 6.
^ Grimaldi, Ralph P. [2004]. Discrete and Combinatorial Mathematics: An applied introduction [ấn bản 5]. Pearson Addison Wesley. ISBN 978-0-201-72634-3.

Số tự nhiên tại MathWorld.

Lấy từ “//vi.wikipedia.org/w/index.php?title=Số_tự_nhiên&oldid=69033266”