Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #takes n integers as input, stores them in a list and returns the list
- def input_list(n):
- lst=[]
- while n>0:
- lst.append(int(input()))
- n-=1
- return lst
- #returns the sum of the numbers in list a[]
- #version 1: iteration by item
- def sum_list_1(a):
- _sum=0
- for num in a:
- _sum+=num
- return _sum
- #returns the sum of the numbers in list a[]
- #version 2: iteration by index
- def sum_list_2(a):
- _sum=0
- for i in range(len(a)):
- _sum+=a[i]
- return _sum
- #write it yourself
- #return the sum of the squares of the numbers in list a[]
- #for example, sum_square([1,2,3]) should return 14
- #def sum_square(a):
- #write it yourself
- #return the average of the numbers in list a[]
- #for example, average([1,2,3]) should return 2.0
- #def average(a):
- #write it yourself
- #return the minimum number in list a[]
- #for example, minimum([1,2,3]) should return 1
- #def minimum(a):
- #write it yourself
- #return the number of odd numbers in list a[]
- #for example, count_odd([1,2,3]) should return 2
- #def count_odd(a):
- #write it yourself
- #return the sum of the even numbers in list a[]
- #for example, sum_even([1,2,3,4]) should return 6
- #def sum_even(a):
- #write it yourself
- #return the sum of the numbers in list a[] until the first negative number is found (excluding the negative number)
- #for example, sum_until_negative([1,2,3,-4,5,6]) should return 6
- #def sum_until_negative(a):
- #returns a list of consecutive sums
- #ret[i] contains the sum of the first i+1 elements of list a[]
- #for example consecutive_sum_1([1,2,3,4]) returns [1,3,6,10]
- #version 1 uses the sum_list_1() function and slicing operator
- def consecutive_sum_1(a):
- ret=[]
- for i in range(len(a)):
- ret.append(sum_list_1(a[0:i+1]))
- return ret
- #returns a list of consecutive sums
- #ret[i] contains the sum of the first i+1 elements of list a[]
- #for example consecutive_sum_2([1,2,3,4]) returns [1,3,6,10]
- #version 2 builds ret[] incrementally and thus is more efficient
- def consecutive_sum_2(a):
- ret=[]
- _sum=0
- for num in a:
- _sum+=num
- ret.append(_sum)
- return ret
- #returns a list of first n fibonacci numbers
- def fibonacci(n):
- fib=[]
- fib.append(0)
- fib.append(1)
- for i in range(2,n):
- fib.append(fib[i-1]+fib[i-2])
- return fib
- #write it yourself
- #return a list of first n prime numbers
- #def prime(n):
- #write it yourself
- #return the largest (having maximum length) sublist of a[] having only nonnegative elements(sublist of a list is similar to substring of a string)
- #for example, largest_nonnegative_sublist([2,-2,-1,1,2,3,-2,1,1,1,2,-1,-2,1]) should return [1,1,1,2]
- #def largest_nonnegative_sublist(a):
- #write it yourself
- #return the sublist of a[] having maximum sum
- #for example, maximum_sum_sublist([2,-3,1,2,3,-5,1,1,1,1]) should return [1,2,3]
- #def maximum_sum_sublist(a):
- #sorts a list of integers in ascending order using bubble sort algorithm
- #bubble_sort() returns nothing, it just modifies the argument list a[]
- #see the animation in the wiki page to have a clearer idea: http://en.wikipedia.org/wiki/Bubble_sort
- def bubble_sort(a):
- for i in range(len(a)-2,-1,-1):
- swapped=False
- for j in range(0,i+1):
- if a[j]>a[j+1]:
- a[j],a[j+1]=a[j+1],a[j]
- swapped=True
- #print(a) #comment in this line to see a simulation of the bubble sort algorithm
- if not swapped:
- return
- #sorts a list of integers in ascending order using selection sort algorithm
- #selection_sort() returns nothing, it just modifies the argument list a[]
- #see the animation in the wiki page to have a clearer idea: http://en.wikipedia.org/wiki/Selection_sort
- def selection_sort(a):
- for i in range(len(a)-1):
- min_index=i
- for j in range(i+1,len(a)):
- if a[j]<a[min_index]:
- min_index=j
- a[i],a[min_index]=a[min_index],a[i]
- #print(a) #comment in this line to see a simulation of the selection sort algorithm
- #write it yourself
- #sort a list of integers in ascending order using counting sort algorithm
- #assume that the elements of a[] are integers in range(10)
- #create a list count[] of length 10, where count[i] holds the number of occurrences of i in a[], for 0<=i<=9
- #for example, for a=[3,5,1,2,3,7,0,0,9,8,4,3,5,6,2], count=[2,1,2,3,1,2,1,1,1,1], because 0 appears twice in a[], 1 appears once in a[] and so on
- #note that, sum_list_1(count) equals len(a) (why?)
- #now create another list ret[] by appending count[i] number of i's, for 0<=i<=9
- #for example, the first two elements of ret[] are 0, the next element is 1, the next two elements are 2 and so on
- #thus ret[] is the sorted version of a[]
- #note that, counting_sort() can not be used to sort non-integral values and the range of integers should be small and known in advance (why?)
- #def counting_sort(a):
- #takes n strings as input, stores them in a list and returns the list
- def input_str_list(n):
- lst=[]
- while n>0:
- lst.append(input())
- n-=1
- return lst
- #write it yourself
- #return the number of strings in list s[] which have length equal to c
- #for example, len_count(["abc","de","fghi","jk","l"],2) should return 2
- #you can use the input_str_list() function above to take a list of strings as input
- #def len_count(s,c):
- #s is a string containing words separated by a single space
- #returns a string containing the words of s in reverse order
- #for example, reverse_sentence("this is good") will return "good is this"
- def reverse_sentence(s):
- words=s.split()
- words.reverse()
- return " ".join(words)
- #write it yourself
- #take a string s as input, which contains words separated by a single space
- #return a string containing each word in its' position but individually reversed
- #for example, reverse_words("this is good") should return "siht si doog"
- #def reverse_words(s):
- #takes n*m integers as input, stores them in a 2D list of n rows and m columns and returns the list
- def input_2D_list(n,m):
- lst=[]
- while n>0:
- lst.append(input_list(m))
- n-=1
- return lst
- #adds two matrices and returns the resultant matrix
- def add_matrices(a,b):
- n=len(a)
- m=len(a[0])
- c=[]
- for i in range(n):
- tmp=[]
- for j in range(m):
- tmp.append(a[i][j]+b[i][j])
- c.append(tmp)
- return c
- #multiplies two matrices and returns the resultant matrix
- def multiply_matrices(a,b):
- p=len(a)
- q=len(a[0])
- r=len(b[0])
- c=[]
- for i in range(p):
- tmp=[]
- for j in range(r):
- _sum=0
- for k in range(q):
- _sum+=a[i][k]*b[k][j]
- tmp.append(_sum)
- c.append(tmp)
- return c
- #write it yourself
- #return a list containing the maximum number of each row of a 2D list a[][]
- #for example, row_maximum([3,1,2],[-3,-1,-2],[1,0,1],[0,0,0]) should return [3,-1,1,0]
- #def row_maximum(a):
- #write it yourself
- #a[] is a list of positive integers
- #return a 2D list of integers ret[][], where ret[i][j] holds the sum of the numbers in the sublist a[i:j] if i<j, 0 otherwise
- #for example, sublist_sum([1,2,3]) should return [[0,1,3,6],[0,0,2,5],[0,0,0,3]]
- #def sublist_sum(a):
- #write it yourself
- #flatten a list a[] of arbitrary dimension
- #for example, flatten([1,[2,3],[[[1]],3],[[[[[1]]]]],2,[1,[2,[3]]]]) should return [1,2,3,1,3,1,2,1,2,3]
- #you might need to use recursion and a global list
- #def flatten(a):
- #returns true if a[][] is an identity matrix, false otherwise
- # http://en.wikipedia.org/wiki/Identity_matrix
- def isIdentity(a):
- n=len(a)
- for i in range(n):
- for j in range(n):
- if i==j:
- if a[i][j]!=1:
- return False
- else:
- if a[i][j]!=0:
- return False
- return True
- #returns the transpose of matrix a[][]
- # http://en.wikipedia.org/wiki/Transpose
- def transpose(a):
- n=len(a)
- m=len(a[0])
- c=[]
- for i in range(m):
- tmp=[]
- for j in range(n):
- tmp.append(a[j][i])
- c.append(tmp)
- return c
- #write it yourself
- #return true if 2D matrix a[][] is symmetric, false otherwise
- # http://en.wikipedia.org/wiki/Symmetric_matrix
- #write 2 versions with and without using the transpose() function
- #def isSymmetric(a):
- #write it yourself
- #return true if 2D matrix a[][] is upper triangular, false otherwise
- # http://en.wikipedia.org/wiki/Triangular_matrix
- #def isUpperTriangular(a):
- #prints 2D list a[][]
- def print_2D_list(a):
- n=len(a)
- m=len(a[0])
- for i in range(n):
- for j in range(m):
- print(repr(a[i][j]).ljust(4),end="")
- print()
- print()
- #returns the number of distinct elements in a list of integers a[]
- def distinct_count(a):
- lst=[]
- for num in a:
- if num not in lst:
- lst.append(num)
- return len(lst)
- #write it yourself
- #return the number of distinct elements in a sorted list of integers a[]
- #write a more efficient version than the previous one
- #def distinct_count_sorted(a):
- #tester of some functions
- def main():
- #test sum_list_1() and sum_list_2()
- #n=int(input())
- #a=input_list(n)
- #print(a)
- #print(sum_list_1(a))
- #print(sum_list_2(a))
- #test consecutive_sum_1() and consecutive_sum_2()
- #n=int(input())
- #a=input_list(n)
- #print(a)
- #print(consecutive_sum_1(a))
- #print(consecutive_sum_2(a))
- #test bubble_sort()
- #n=int(input())
- #a=input_list(n)
- #print(a)
- #bubble_sort(a)
- #print(a)
- #test selection_sort()
- #n=int(input())
- #a=input_list(n)
- #print(a)
- #selection_sort(a)
- #print(a)
- #test reverse_sentence()
- #s=input()
- #print(reverse_sentence(s))
- #test add_matrices()
- #n=int(input())
- #m=int(input())
- #a=input_2D_list(n,m)
- #b=input_2D_list(n,m)
- #print_2D_list(a)
- #print_2D_list(b)
- #c=add_matrices(a,b)
- #print_2D_list(c)
- #test multiply_matrices()
- #p=int(input())
- #q=int(input())
- #r=int(input())
- #a=input_2D_list(p,q)
- #b=input_2D_list(q,r)
- #print_2D_list(a)
- #print_2D_list(b)
- #c=multiply_matrices(a,b)
- #print_2D_list(c)
- print()
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement