برای استفاده از امکانات سیستم، گزینه جاوا اسکریپت در مرورگر شما باید فعال باشد
صفحه
از
0
Programming challenges : the programming contest training manual
Skiena, Steven S.
اطلاعات کتابشناختی
Programming challenges : the programming contest training manual
Author :
Skiena, Steven S.
Publisher :
Springer,
Pub. Year :
2003
Subjects :
Computer programming.
Call Number :
QA 76 .6 .S598 2003
جستجو در محتوا
ترتيب
شماره صفحه
امتياز صفحه
فهرست مطالب
Programming Challenges
(1)
Contents
(13)
1 Getting Started
(21)
1.1 Getting Started With the Judge
(21)
1.1.1 The Programming Challenges Robot Judge
(22)
1.1.2 The Universidad de Valladolid Robot Judge
(22)
1.1.3 Feedback From the Judge
(23)
1.2 Choosing Your Weapon
(24)
1.2.1 Programming Languages
(25)
1.2.2 Reading Our Programs
(26)
1.2.3 Standard Input/Output
(27)
1.3 Programming Hints
(29)
1.4 Elementary Data Types
(31)
1.5 About the Problems
(33)
1.6 Problems
(35)
1.6.1 The 3n + 1 Problem
(35)
1.6.2 Minesweeper
(36)
1.6.3 The Trip
(37)
1.6.4 LCD Display
(38)
1.6.5 Graphical Editor
(39)
1.6.6 Interpreter
(41)
1.6.7 Check the Check
(43)
1.6.8 Australian Voting
(45)
1.7 Hints
(46)
1.8 Notes
(46)
2 Data Structures
(47)
2.1 Elementary Data Structures
(47)
2.1.1 Stacks
(48)
2.1.2 Queues
(48)
2.1.3 Dictionaries
(50)
2.1.4 Priority Queues
(51)
2.1.5 Sets
(52)
2.2 Object Libraries
(53)
2.2.1 The C++ Standard Template Library
(53)
2.2.2 The Java java.util Package
(53)
2.3 Program Design Example: Going to War
(54)
2.4 Hitting the Deck
(55)
2.5 String Input/Output
(57)
2.6 Winning the War
(58)
2.7 Testing and Debugging
(59)
2.8 Problems
(62)
2.8.1 Jolly Jumpers
(62)
2.8.2 Poker Hands
(63)
2.8.3 Hartals
(65)
2.8.4 Crypt Kicker
(67)
2.8.5 Stack 'em Up
(68)
2.8.6 Erd¨os Numbers
(70)
2.8.7 Contest Scoreboard
(72)
2.8.8 Yahtzee
(73)
2.9 Hints
(75)
2.10 Notes
(75)
3 Strings
(76)
3.1 Character Codes
(76)
3.2 Representing Strings
(78)
3.3 Program Design Example: Corporate Renamings
(79)
3.4 Searching for Patterns
(81)
3.5 Manipulating Strings
(82)
3.6 Completing the Merger
(83)
3.7 String Library Functions
(84)
3.8 Problems
(86)
3.8.1 WERTYU
(86)
3.8.2 Where's Waldorf?
(87)
3.8.3 Common Permutation
(89)
3.8.4 Crypt Kicker II
(90)
3.8.5 Automated Judge Script
(91)
3.8.6 File Fragmentation
(93)
3.8.7 Doublets
(94)
3.8.8 Fmt
(95)
3.9 Hints
(97)
3.10 Notes
(97)
4 Sorting
(98)
4.1 Sorting Applications
(98)
4.2 Sorting Algorithms
(99)
4.3 Program Design Example: Rating the Field
(102)
4.4 Sorting Library Functions
(103)
4.5 Rating the Field
(105)
4.6 Problems
(108)
4.6.1 Vito's Family
(108)
4.6.2 Stacks of Flapjacks
(109)
4.6.3 Bridge
(111)
4.6.4 Longest Nap
(112)
4.6.5 Shoemaker's Problem
(114)
4.6.6 CDVII
(115)
4.6.7 ShellSort
(117)
4.6.8 Football (aka Soccer)
(119)
4.7 Hints
(121)
4.8 Notes
(121)
5 Arithmetic and Algebra
(122)
5.1 Machine Arithmetic
(122)
5.1.1 Integer Libraries
(123)
5.2 High-Precision Integers
(123)
5.3 High-Precision Arithmetic
(125)
5.4 Numerical Bases and Conversion
(130)
5.5 Real Numbers
(132)
5.5.1 Dealing With Real Numbers
(133)
5.5.2 Fractions
(133)
5.5.3 Decimals
(134)
5.6 Algebra
(135)
5.6.1 Manipulating Polynomials
(135)
5.6.2 Root Finding
(136)
5.7 Logarithms
(136)
5.8 Real Mathematical Libraries
(137)
5.9 Problems
(139)
5.9.1 Primary Arithmetic
(139)
5.9.2 Reverse and Add
(140)
5.9.3 The Archeologist's Dilemma
(141)
5.9.4 Ones
(142)
5.9.5 A Multiplication Game
(143)
5.9.6 Polynomial Coefficients
(144)
5.9.7 The Stern-Brocot Number System
(145)
5.9.8 Pairsumonious Numbers
(147)
5.10 Hints
(148)
5.11 Notes
(148)
6 Combinatorics
(149)
6.1 Basic Counting Techniques
(149)
6.2 Recurrence Relations
(151)
6.3 Binomial Coefficients
(151)
6.4 Other Counting Sequences
(153)
6.5 Recursion and Induction
(155)
6.6 Problems
(157)
6.6.1 How Many Fibs?
(157)
6.6.2 How Many Pieces of Land?
(158)
6.6.3 Counting
(159)
6.6.4 Expressions
(160)
6.6.5 Complete Tree Labeling
(161)
6.6.6 The Priest Mathematician
(162)
6.6.7 Self-describing Sequence
(164)
6.6.8 Steps
(165)
6.7 Hints
(166)
6.8 Notes
(166)
7 Number Theory
(167)
7.1 Prime Numbers
(167)
7.1.1 Finding Primes
(168)
7.1.2 Counting Primes
(169)
7.2 Divisibility
(169)
7.2.1 Greatest Common Divisor
(170)
7.2.2 Least Common Multiple
(171)
7.3 Modular Arithmetic
(172)
7.4 Congruences
(174)
7.4.1 Operations on Congruences
(174)
7.4.2 Solving Linear Congruences
(175)
7.4.3 Diophantine Equations
(175)
7.5 Number Theoretic Libraries
(176)
7.6 Problems
(177)
7.6.1 Light, More Light
(177)
7.6.2 Carmichael Numbers
(178)
7.6.3 Euclid Problem
(179)
7.6.4 Factovisors
(180)
7.6.5 Summation of Four Primes
(181)
7.6.6 Smith Numbers
(182)
7.6.7 Marbles
(183)
7.6.8 Repackaging
(184)
7.7 Hints
(186)
7.8 Notes
(186)
8 Backtracking
(187)
8.1 Backtracking
(187)
8.2 Constructing All Subsets
(189)
8.3 Constructing All Permutations
(190)
8.4 Program Design Example: The Eight-Queens Problem
(192)
8.5 Pruning Search
(193)
8.6 Problems
(196)
8.6.1 Little Bishops
(196)
8.6.2 15-Puzzle Problem
(197)
8.6.3 Queue
(199)
8.6.4 Servicing Stations
(200)
8.6.5 Tug of War
(201)
8.6.6 Garden of Eden
(202)
8.6.7 Color Hash
(204)
8.6.8 Bigger Square Please
(206)
8.7 Hints
(208)
8.8 Notes
(208)
9 Graph Traversal
(209)
9.1 Flavors of Graphs
(209)
9.2 Data Structures for Graphs
(211)
9.3 Graph Traversal: Breadth-First
(214)
9.3.1 Breadth-First Search
(214)
9.3.2 Exploiting Traversal
(215)
9.3.3 Finding Paths
(216)
9.4 Graph Traversal: Depth-First
(218)
9.4.1 Finding Cycles
(218)
9.4.2 Connected Components
(219)
9.5 Topological Sorting
(220)
9.6 Problems
(223)
9.6.1 Bicoloring
(223)
9.6.2 Playing With Wheels
(224)
9.6.3 The Tourist Guide
(226)
9.6.4 Slash Maze
(228)
9.6.5 Edit Step Ladders
(230)
9.6.6 Tower of Cubes
(231)
9.6.7 From Dusk Till Dawn
(233)
9.6.8 Hanoi Tower Troubles Again!
(235)
9.7 Hints
(236)
10 Graph Algorithms
(237)
10.1 Graph Theory
(237)
10.1.1 Degree Properties
(237)
10.1.2 Connectivity
(238)
10.1.3 Cycles in Graphs
(239)
10.1.4 Planar Graphs
(240)
10.2 Minimum Spanning Trees
(240)
10.3 Shortest Paths
(243)
10.3.1 Dijkstra's Algorithm
(243)
10.3.2 All-Pairs Shortest Path
(245)
10.4 Network Flows and Bipartite Matching
(247)
10.5 Problems
(251)
10.5.1 Freckles
(251)
10.5.2 The Necklace
(252)
10.5.3 Fire Station
(254)
10.5.4 Railroads
(255)
10.5.5 War
(257)
10.5.6 Tourist Guide
(259)
10.5.7 The Grand Dinner
(261)
10.5.8 The Problem With the Problem Setter
(262)
10.6 Hints
(264)
11 Dynamic Programming
(265)
11.1 Don't Be Greedy
(265)
11.2 Edit Distance
(266)
11.3 Reconstructing the Path
(270)
11.4 Varieties of Edit Distance
(271)
11.5 Program Design Example: Elevator Optimization
(273)
11.6 Problems
(277)
11.6.1 Is Bigger Smarter?
(277)
11.6.2 Distinct Subsequences
(278)
11.6.3 Weights and Measures
(279)
11.6.4 Unidirectional TSP
(280)
11.6.5 Cutting Sticks
(282)
11.6.6 Ferry Loading
(283)
11.6.7 Chopsticks
(285)
11.6.8 Adventures in Moving: Part IV
(286)
11.7 Hints
(287)
11.8 Notes
(287)
12 Grids
(288)
12.1 Rectilinear Grids
(288)
12.1.1 Traversal
(289)
12.1.2 Dual Graphs and Representations
(290)
12.2 Triangular and Hexagonal Grids
(291)
12.2.1 Triangular Lattices
(291)
12.2.2 Hexagonal Lattices
(292)
12.3 Program Design Example: Plate Weight
(295)
12.4 Circle Packings
(297)
12.5 Longitude and Latitude
(298)
12.6 Problems
(299)
12.6.1 Ant on a Chessboard
(299)
12.6.2 The Monocycle
(300)
12.6.3 Star
(302)
12.6.4 Bee Maja
(303)
12.6.5 Robbery
(304)
12.6.6 (2/3/4)-D Sqr/Rects/Cubes/Boxes?
(306)
12.6.7 Dermuba Triangle
(307)
12.6.8 Airlines
(308)
12.7 Hints
(310)
13 Geometry
(311)
13.1 Lines
(311)
13.2 Triangles and Trigonometry
(314)
13.2.1 Right Triangles and the Pythagorean Theorem
(315)
13.2.2 Trigonometric Functions
(315)
13.2.3 Solving Triangles
(316)
13.3 Circles
(318)
13.4 Program Design Example: Faster Than a Speeding Bullet
(319)
13.5 Trigonometric Function Libraries
(322)
13.6 Problems
(324)
13.6.1 Dog and Gopher
(324)
13.6.2 Rope Crisis in Ropeland!
(325)
13.6.3 The Knights of the Round Table
(326)
13.6.4 Chocolate Chip Cookies
(327)
13.6.5 Birthday Cake
(328)
13.6.6 The Largest/Smallest Box
(329)
13.6.7 Is This Integration?
(330)
13.6.8 How Big Is It?
(331)
13.7 Hints
(332)
14 Computational Geometry
(333)
14.1 Line Segments and Intersection
(333)
14.2 Polygons and Angle Computations
(335)
14.3 Convex Hulls
(336)
14.4 Triangulation: Algorithms and Related Problems
(339)
14.4.1 Van Gogh's Algorithm
(340)
14.4.2 Area Computations
(342)
14.4.3 Point Location
(342)
14.5 Algorithms on Grids
(344)
14.5.1 Range Queries
(344)
14.5.2 Lattice Polygons and Pick's Theorem
(345)
14.6 Geometry Libraries
(346)
14.7 Problems
(347)
14.7.1 Herding Frosh
(347)
14.7.2 The Closest Pair Problem
(348)
14.7.3 Chainsaw Massacre
(349)
14.7.4 Hotter Colder
(350)
14.7.5 Useless Tile Packers
(351)
14.7.6 Radar Tracking
(353)
14.7.7 Trees on My Island
(354)
14.7.8 Nice Milk
(356)
14.8 Hints
(357)
A Appendix
(359)
A.1 The ACM International Collegiate Programming Contest
(359)
A.1.1 Preparation
(360)
A.1.2 Strategies and Tactics
(361)
A.2 International Olympiad in Informatics
(363)
A.2.1 Participation
(363)
A.2.2 Format
(364)
A.2.3 Preparation
(365)
A.3 Topcoder.com
(365)
A.4 Go to Graduate School!
(366)
A.5 Problem Credits
(368)
References
(370)
Index
(373)
