Home >Business >Soal latihan algoritma

Soal latihan algoritma

Date post:11-May-2015
Category:
View:21,042 times
Download:12 times
Share this document with a friend
Transcript:
  • 1.[Club Pemrograman Java]Buku Latihan Algoritma Author:Hayi Nukman STMIK AKAKOM Yogyakarta July 2011

2. Petunjuk An algorithm must be seen to be believed. Buku ini terdiri dari enam bagian yang masing-masing berisi beberapasoal/case. Tugas anda adalah: Mencari minimal 3 (tiga) cara penyelesaian/algoritma yang berbeda untuk masing-masing case. Buat Program dari algoritma-algoritma tersebut (Java/C/C++). Kemudian buat catatan singkat mengenai Algoritma yang Anda Gu- nakan untuk menyelesaikan kasus tersebut. Post ke Blog anda, kemudian kirimkan link posting tersebut kehayi.nkm@gmail.com email: (Bila perlu disertai dengan source code program dalam bentuk Attach- ment).Contoh: UVA: 154 - Recycling Recycling Kerbside recycling has come to New Zealand, and every city from Auckland to Invercargill has leapt on to the band wagon. The bins come in 5 dierent coloursred, orange, yellow, green and blueand 5 wastes have been identied for recyclingPlastic, Glass, Aluminium, Steel, and Newspaper. Obviously there has been no coordination between cities, so each city has allocated wastes to bins in an arbitrary fashion. Now that the government has solved the minor problems of today (such asi 3. ii reorganising Health, Welfare and Education), they are looking around for further challenges. The Minister for Environmental Doodads wishes to introduce the Regularisation of Allocation of Solid Waste to Bin Colour Bill to Parliament, but in order to do so needs to determine an allocation of his own. Being a rm believer in democracy (well some of the time anyway), he surveys all the cities that are using this recycling method. From these data he wishes to determine the city whose allocation scheme (if imposed on the rest of the country) would cause the least impact, that is would cause the smallest number of changes in the allocations of the other cities. Note that the sizes of the cities is not an issue, after all this is a democracy with the slogan One City, One Vote.Write a program that will read in a series of allocations of wastes to bins and determine which citys allocation scheme should be chosen. Note that there will always be a clear winner. Input and Output Input will consist of a series of blocks. Each block will consist of a series of lines and each line will contain a series of allocations in the form shown in the example. There may be up to 100 cities in a block. Each block will be terminated by a line starting with e. The entire le will be terminated by a line consisting of a single #.Output will consist of a series of lines, one for each block in the input. Each line will consist of the number of the city that should be adopted as a national example. Sample input: r/P,o/G,y/S,g/A,b/N r/G,o/P,y/S,g/A,b/N r/P,y/S,o/G,g/N,b/A r/P,o/S,y/A,g/G,b/N e r/G,o/P,y/S,g/A,b/N r/P,y/S,o/G,g/N,b/A r/P,o/S,y/A,g/G,b/N r/P,o/G,y/S,g/A,b/N ecclesiastical # 4. iiiSample output14Case review:1st Algorithm: Brute ForceFor each city, iterate through every other city, and count the numberof dierences. So, keep a counter, and if city[i]s red bin != city[j]sred bin, add one to the count.Output the city with the fewest dierences.Source:Your Code here....2nd Algorithm: Brute ForceMake an array of chars [100][5] where a[i][0] is the color of the plasticbin, a[i][1] is the color of the glass bin, and so on. Then compare eachcity brute force against all other cities, and return the most optimalone.Source:Your Code here....dan seterusnya.Catatan: Review sebaiknya menggunakan Bahasa Inggris (tidak diharuskan). Boleh lebih dari 3 cara. Utamakan bagaimana penyelesaian kasus terlebih dahulu, optimalisasialgoritma bisa belakangan. 5. iv Algoritma kedua dan seterusnya boleh berupa optimalisasi dari algo- ritma pertama atau algoritma-algoritma sebelumnya.Regards. Hayi Nukman (July 2011),aCreated with: L TEX. 6. Daftar Isi Recycling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i1 Easy11.1 The Blocks Problem .. . . . . . . . . . . . . . . . . . . . . . 11.2 Greedy Gift Givers . .. . . . . . . . . . . . . . . . . . . . . . 41.3 Number Chains . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 The Bases Are Loaded. . . . . . . . . . . . . . . . . . . . . . 81.5 Combinations . . . . .. . . . . . . . . . . . . . . . . . . . . . 92 Medium112.1 Lining Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 The Tower of Babylon . . . .. . . . . . . . . . . . . . . . . . 122.3 Points in Figures: Rectangles . . . . . . . . . . . . . . . . . . 142.4 King . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 162.5 Number Maze . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Hard233.1 Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 The Probable n-Ascendants . . . . . . . . . . . . . . . . . . . 253.3 Poker Hands . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Math314.1 LCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Minimum Sum LCM . . . . . . . . . . . . . . . . . . . . . . . 324.3 Hendrie Sequence . . .. . . . . . . . . . . . . . . . . . . . . . 354.4 Modular Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . 364.5 Polynomial coecients . . . . . . . . . . . . . . . . . . . . . . 384.6 Pizza Cutting . . . . . . . . . . . . . . . . . . . . . . . . . . . 39v 7. viDAFTAR ISI5 Sorting and Searching435.1 Crossword Answers . . . . . . . . . . . . . . . . . . . . . . . .435.2 The Department of Redundancy Department . . . . . . . . . .475.3 Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . 486 Other 516.1 Group Reverse . . . . . . . . . . . . . . . . . . . . . . . . . . 516.2 Testing the CATCHER . . . . . . . . . . . . . . . . . . . . . . 526.3 The Settlers of Catan . . . . . . . . . . . . . . . . . . . . . . . 54 8. BAB 1 Easy Go for the happy endings, because life doesnt have any sequels. 1.1 The Blocks Problem Background Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks. In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specied state, you will program a robotic arm to respond to a limited set of commands. The Problem The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a at table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all 0 i < n 1 as shown in the diagram below:Figure: InitialBlocks WorldThe valid commands for the robot arm that manipulates blocks are: * move a onto b1 9. 2 BAB 1. EASYwhere a and b are block numbers, puts block a onto block b after return-ing any blocks that are stacked on top of blocks a and b to their initialpositions.* move a over bwhere a and b are block numbers, puts block a onto the top of the stackcontaining block b, after returning any blocks that are stacked on top ofblock a to their initial positions.* pile a onto bwhere a and b are block numbers, moves the pile of blocks consisting ofblock a, and any blocks that are stacked above block a, onto block b. Allblocks on top of block b are moved to their initial positions prior to thepile taking place. The blocks stacked above block a retain their orderwhen moved.* pile a over bwhere a and b are block numbers, puts the pile of blocks consisting ofblock a, and any blocks that are stacked above block a, onto the top ofthe stack containing block b. The blocks stacked above block a retaintheir original order when moved.* quitterminates manipulations in the block world.Any command in which a = b or in which a and b are in the samestack of blocks is an illegal command. All illegal commands should beignored and should have no aect on the conguration of blocks.The InputThe input begins with an integer n on a line by itself representing thenumber of blocks in the block world. You may assume that 0 0. Then just implement the four functions carefully.1.2 Greedy Gift GiversThe ProblemThis problem involves determining, for a group of gift-giving friends, howmuch more each person gives than they receive (and vice versa for thosethat view gift-giving with cynicism). In this problem each person sets aside some money for gift-giving anddivides this money evenly among all those to whom gifts are given. However, in any group of friends, some people are more giving thanothers (or at least may have more acquaintances) and some people havemore money than others. Given a group of friends, the money each person in the group spendson gifts, and a (sub)list of friends to whom each person gives gifts; youare to write a program that determines how much more (or less) eachperson in the group gives than they receive.The InputThe input is a sequence of gift-giving groups. A group consists of severallines: the number of people in the group, a list of the names of each person in the group, a line for each person in the group consisting of the name of theperson, the amount of money spent on gifts, the number of peopleto whom gifts are given, and the names of those to whom gifts aregiven. All names are lower-case letters, there are no more than 10 people ina group, and no name is more than 12 characters in length. Money is anon-negative integer less than 2000. 12. 5The input consists of one or more groups and is terminated by end-of-le.The OutputFor each group of gift-givers, the name of each person in the group shouldbe printed on a line followed by the net gain (or loss) received (or spent)by the person. Names in a group should be printed in the same order inwhich they rst appear in the input. The output for each group should be separated from other groups bya blank line. All gifts are integers. Each person gives the same integeramount of money to each fr

Embed Size (px)
Recommended