Wikiversity

Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 1

< Algorithms -- 2009-2010 -- info.uvt.ro

Quick links: front; laboratories agenda, 1, 2, 3, 4, 5, 6, 7, evaluation, tools, references.

Notes

edit
  • Laboratory / seminar problem set 1:

Exercises

edit

From the problem set above, exercises:

  • problem 7 (for en), or problem 8 (for ro), points:
    • a: Computing the sum of all digits of number n. For instance for n = 26326 one obtains the value 19.
    • f: Deciding if n is prime or not (the algorithm should return true if the number is prime and false otherwise.
    • g: Decomposing n in prime factors. For instance for 490 = 2^1 * 5^1 * 7^2 one obtains the following set of prime factors: {2, 5, 7} and their corresponding exponents: {1, 1, 2}.

Assignment

edit

For submission please follow: assignment 1.

From the problem set above, exercises:

  • problem 7 (for en), or problem 8 (for ro), points:
    • c: Constructing the set of all digits of n. For instance, for the value 26326 one obtain the set {2, 3, 6}. Hints:
      • use a list with 10 elements (from 0 to 9) with boolean values (True or False);
    • d: Finding all binary digits of n.
      • use a list to hold the digits (to print them in the correct order);
    • e: Finding all proper divisors of n (divisors which are not 1 or n).

Solutions to exercises

edit
  • the sum of the digits of a number:
n = input ("n = ")
s = 0
while n > 0 :
    d = n % 10
    n = n / 10
    s += d
print s
  • deciding if a number is prime or not:
from math import sqrt

n = input ("n = ")

# p -> if n is prime or not
if n <= 1 :
    p = False
elif n <= 3 :
    p = True
elif n % 2 == 0 :
    p = False
else :
    l = int (sqrt (n))
    p = True
    for d in range (3, l + 1, 2) :
        if n % d == 0 :
            p = False
            break

if p :
    print "prime"
else :
    print "not prime"
  • determining the prime factors of a number:
    • variant a:
from math import sqrt

n = input ("n = ")

for d in range (2, int (sqrt (n)) + 1) :
    c = 0
    while n % d == 0 :
        c += 1
        n /= d
    if c > 0 :
        print d, "^", c
    • variant b:
n = input ("n = ")
d = 2
c = 0
while n > 1 :
    if n % d == 0 :
        c += 1
        n /= d
    else :
        if c > 0 :
            print d, "^", c
        d += 1
        c = 0
if c > 0 :
    print d, "^", c

Ciprian Dorin Crăciun, ccraciun@info.uvt.ro

Retrieved from "https://beta.wikiversity.org/w/index.php?title=Algorithms_--_2009-2010_--_info.uvt.ro/Laboratory_1&oldid=194166"