CS-Assignment 1:Solution

Description

In this assignment, you will implement two algorithms as three complete Python programs. The Python statements: if, for, if – else, and while are outlined below.

Use these to recognize the Python statement needed to translated the algorithm into a complete program!

Algorithm 1

Compute the product of two positive integers using the multiplication algorithm of the ancient Egyptians.

Three Sample Runs

Enter x: 14

Enter y: 12

14*12=168

Enter x: 4891

Enter y: 52

4891 * 52 = 254332

Enter x: 72890346

Enter y: 35619

72890346 * 35619 = 2596281234174

Final Touches

In order to show explicitly what this algorithm is doing (those ancient Egyptians were busy), we shall use formatting to display x, y, and product each time through the loop to produce a table with borders of three columns illustrated below. Here are two runs:

Enter x: 14

Enter y: 12

——————————————————-

x y product

——————————————————-

14	12	0
6	28	0
3	56	0
2	56	56
1	112	56
0	112	168

——————————————————-

14*12=168

Enter x: 72890346

Enter y: 35619

——————————————————-

x y product

——————————————————-

72890346	35619	0
35618	72890346	72890346
17809	145780692	72890346
17808	145780692	218671038
8904	291561384	218671038
4452	583122768	218671038
2226	1166245536	218671038
1113	2332491072	218671038
1112	2332491072	2551162110
556	4664982144	2551162110
278	9329964288	2551162110
139	18659928576	2551162110
138	18659928576	21211090686
69	37319857152	21211090686
68	37319857152	58530947838
34	74639714304	58530947838
17	149279428608	58530947838
16	149279428608	207810376446
8	298558857216	207810376446
4	597117714432	207810376446
2	1194235428864	207810376446
1	2388470857728	207810376446
0	2388470857728	2596281234174

——————————————————-

72890346 * 35619 = 2596281234174

Algorithm 2

Input a string of digits (e.g., ‘72890346’) and an integer representing the number of digits in each group (e.g., 3). From among the consecutive products of each group of three, determine the maximum.

7 x 2 x 8 = 112

2 x 8 x 9 = 144 <- maximum

8 x 9 x 0 = 0

9 x 0 x 3 = 0

0 x 3 x 4 = 12

3 x 4 x 6 = 72

You will need to create a user-defined function product(dig, indx, snum) that computes the product of dig consecutive digits, starting at index indx in the string of digits snum. For example, if indx = 5, dig

• 3, and snum = ‘72890346’, the function call product(3, 5, ‘72890346’) returns 144, the product of

3 x 4 x 6 back to the caller.

Three Sample runs:

Enter an integer: 491773

Number of digits in a product: 2

The max product of 2 consecutive digits in 491773 is 49

Enter an integer: 72890346

Number of digits in a product: 3

The max product of 3 consecutive digits in 72890346 is 144

Enter an integer: 845801561660979191338754992

Number of digits in a product: 6

The max product of 6 consecutive digits in 845801561660979191338754992 is 90720

Finishing Touches

Modify your program to allow the user (you) to enter the number of runs you wish to execute. Here is a single execution of this program.

Enter the number of runs: 4

Enter an integer: 2315891

Number of digits in a product: 3

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450