Scribd
Upload
10 views2 pages

PT TK GT 4 Eng

The document outlines Lab #4 focused on implementing problems using the 'Decrease and Conquer' technique, including Topological Sorting, the Josephus problem, the Selection problem, and Interpolation Search. Each problem specifies input and output formats along with examples. Additionally, it includes file submission regulations and consequences for plagiarism or cheating.

Uploaded by

ngongocly204
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

PT TK GT 4 Eng

The document outlines Lab #4 focused on implementing problems using the 'Decrease and Conquer' technique, including Topological Sorting, the Josephus problem, the Selection problem, and Interpolation Search. Each problem specifies input and output formats along with examples. Additionally, it includes file submission regulations and consequences for plagiarism or cheating.

Uploaded by

ngongocly204
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Lab #4: Decrease and Conquer

Students implemented the following problems using "Decrease and Conquer" technique.

1. Topological Sorting:
Input Output
Content of the "input_1.txt" file:
- Dòng thứ 1: positve integer n represent the number of courses.
Topology order of courses.
- Next klines: Courses relationships.
- End with 0.
Example:
5
3 1 2 (1 and 2 need to be done before 3)
12345
43 (3 need to be done before 4)
5 3 4 (3 and 4 need to be done before 5)
0

2. Josephus problem: Let n people stand in a circle. Starting the count with person number 1,
we eliminate every second person until only one survivor is left. The problem is to determine the
survivor’s number J(n).
Input Output
Content of the "input_2.txt" file:
- Eliminated people (time order)
- Positive integer n represent the
- Last survivor.
amount of people in the circle.
Example: 2415
5 3

3. Selection problem: Finding the k th smallest number in an array S = {s1 , s2 , ..., sn } với k ∈ [1, n]

Input Output
Content of the "input_3.txt" file:
- 1st line: positive integer n represent size of the given array.
- k th smallest number required.
- 2nd line: n real numbers separated by a single space " ".
- 3rd line: positive integer k
Example:
5
3.3
1.1 7.3 2.5 4.6 3.3
3
4. Interpolation Search: Find the value k from the given array which has n elements.
Input Output
Content of the "input_4.txt" file:
- 1st line: positive integer n represent size of the given array
- 2nd line: n real numbers sorted ascendingly. Separated by - Position (from 0) of x.
a single space " ".
- 3rd line: Required real x number
Example:
5
1
1.1 2.2 3.3 4.4 5.5
2.2

• FILE SUBMISSION REGULATION


– Only submit files with .cpp extensions: 1.cpp, 2-1.cpp, 2-2.cpp ... . Project submission
is illegal.
– .cpp files must be located in MSSV folder, then be compressed into MSSV.zip(.rar).
– Source code must receive input and return output as specified for each problem. Submissions
with wrong regulation will result in a "0" (zero).
– Plagiarism and Cheating will result in a "0" (zero) for the entire course.
– Contact: bhthong@fit.hcmus.edu.vn for more information.

END

You might also like