September 18, 2015 9:00 AM
We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:
1) Write a recursive function to find the sum of the first n odd integers. For instance, if n = 2, the first two odd integers are 1 and 3, and their sum is 4.
2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.
3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.
Your task is to solve the three homework exercises given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
Scala:
// https://programmingpraxis.com/2015/09/18/three-homework-problems-2/ // 1) def sumNOdd(n: Int): Int = if (n < 1) 0 else ((n - 1) * 2 + 1) + sumNOdd(n - 1) // by the way =n*n // 2) def freq(s: String, c: Char): Int = s.filter(_ == c).size // 3) def caesarEnc(s: String, key: Char): String = s.map(c => if (c != ' ') ((c - 'A' + key - 'A') % ('Z' - 'A' + 1) + 'A').toChar else ' ') caesarEnc("ATTACK AT DAWN", 'F') //> res13: String = FYYFHP FY IFBS def caesarDec(s: String, key: Char): String = s.map(c => if (c != ' ') ('A' + (c - key + 'Z' - 'A' + 1) % ('Z' - 'A' + 1)).toChar else ' ') caesarDec(caesarEnc("ATTACK AT DAWN", 'F'), 'F')//> res14: String = ATTACK AT DAWNBy FA on September 18, 2015 at 10:29 AM
I hope this isn’t another formatting disaster, but I flipped out thirty years ago when a homework exercise assumed ASCII encoding without comment (one of my worst overreactions, I walked out of the whole course when my solution was criticized for not making that unstated assumption), and I feel the need of a friendly objection today when a suggested solution assumes that any character fits in an octet. Here’s counting UTF-8 Greek letters from today’s Βικιπαίδεια front page :) In Python 3, copy-pasting in Lubuntu to Firefox from an Emacs running in Red Hat over SSH. Who do we blame if it gets mangled? Everything looks fine to me at the moment, a second before posting.
text = '''Ο Σαίρεν Κίρκεγκωρ, στα Δανικά Søren Aabye Kierkegaard, 5 Μαΐου 1813 – 11 Νοεμβρίου 1855), ήταν Δανός φιλόσοφος και θεολόγος του 19ου αιώνα. Θεωρείται ο πρώτος υπαρξιστής φιλόσοφος.''' from collections import Counter print(*Counter(c for c in text if c.isalpha()) .most_common(15), sep = '\n')The output:
('ο', 13) ('α', 11) ('ρ', 7) ('ι', 7) ('ς', 6) ('τ', 6) ('ε', 6) ('υ', 5) ('ν', 5) ('e', 4) ('φ', 4) ('κ', 4) ('σ', 4) ('ό', 4) ('ί', 4)By Jussi Piitulainen on September 18, 2015 at 12:42 PM
def sum_odd(n): if n < 1: return 0 else: return 2*n-1 + sum_odd(n-1) def count_frequence(s): from collections import Counter return dict(Counter(s)) def ceasar(s, shift): import string alphabet = list(string.ascii_letters) return "".join(alphabet[(alphabet.index(c)+shift)%len(alphabet)] if c in alphabet else c for c in s) print sum_odd(2) print count_frequence("hello") print ceasar("dont attack gallia!", 5) # output: # 4 # {'h': 1, 'e': 1, 'l': 2, 'o': 1} # itsy fyyfhp lfqqnf!By Rutger on September 18, 2015 at 1:37 PM
1 in SML, 2 and 3 in Perl:
(* tail recursive solution that counts upwards from 1 O(N) - only touches each odd number up to N *) fun sumFirstNOdds n = let fun loop curr count acc = if count = n then acc else case (curr mod 2) of 1 => loop (curr + 2) (count + 1) (acc + curr) | _ => loop (curr + 1) count acc in loop 1 0 0 end (* closed form formula SUM( odd(x) | x >= 1 and x <= N ) = N^2 *) fun sumFirstNOdds2 n = n * n; use strict; use warnings; # O(n) word frequency using ascii ordinal values sub frequency { my ($s) = @_; my @ascii_table = (0) x 128; foreach my $char ( split //, $s ) { $ascii_table[ ord $char ]++; } return @ascii_table; } print join(',', frequency('hello')), "\n"; # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, # 0,0,1,0,0,1,0,0,0,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 # 'e' 'h' 'l' 'o' sub encrypt { my ($plaintext, $shift) = @_; my @letters = ('A' .. 'Z'); return join '', map { ($_ ge 'A' && $_ le 'Z') ? $letters[(ord($_) + $shift - ord('A')) % @letters] : $_ } split //, $plaintext; } sub decrypt { my ($plaintext, $shift) = @_; return encrypt($plaintext, -$shift); } print decrypt(encrypt('ATTACK AT DAWN',5),5), "\n"; # ATTACK AT DAWNBy mcmillhj on September 18, 2015 at 7:49 PM
A Haskell version, using part of Jussi Piitulainen’s text for the character frequency problem.
import Data.Char (chr, ord) import Data.List (group, sort, sortBy) import Data.Ord (Down(..), comparing) import Text.Printf (printf) -- The sum of the first n odd numbers. A more idiomatic way to write it would -- be: -- oddSum n = sum [1, 3 .. 2*n-1] -- -- but I interpret the question as asking for explicit recursion. oddSum :: Int -> Int oddSum n = go (2*n-1) where go i | i > 0 = i + go (i-2) | otherwise = 0 -- The number of occurrences of each element of a list, sorted by decreasing -- frequency. freq :: (Eq a, Ord a) => [a] -> [(a, Int)] freq = order . map (\xs@(x:_) -> (x, length xs)) . group . sort where order = sortBy (comparing (Down . snd)) -- A pair of functions to perform Caesar encryption and decryption for a given -- key. caesar :: Int -> (String -> String, String -> String) caesar n = let m = n `mod` 26 in (crypt m, crypt (26 - m)) where crypt k = unwords . map (cryptWord k) . words cryptWord k = map (toChar . rot k . fromChar) fromChar x = ord x - ord 'A' toChar x = chr (x + ord 'A') rot k x = (x + k) `rem` 26 main :: IO () main = do -- Sum of odd numbers let n = 7 printf "Sum of the first %d odd numbers: %d\n\n" n (oddSum n) -- Letter frequencies let s = "Ο Σαίρεν Κίρκεγκωρ, στα" printf "Letter frequencies for: %s\n" s mapM_ (uncurry (printf " %c %d\n")) (freq s) putStrLn "" -- Caesar encryption and decryption let key = 5 (encrypt, decrypt) = caesar key sourceText = "ATTACK AT DAWN" cipherText = encrypt sourceText plainText = decrypt cipherText printf "Caesar encryption and decryption with key %d.\n" key printf " %s => %s\n" sourceText cipherText printf " %s => %s\n" cipherText plainText$ ./hmwrk3 Sum of the first 7 odd numbers: 49 Letter frequencies for: Ο Σαίρεν Κίρκεγκωρ, στα 3 ρ 3 ί 2 α 2 ε 2 κ 2 , 1 Κ 1 Ο 1 Σ 1 γ 1 ν 1 σ 1 τ 1 ω 1 Caesar encryption and decryption with key 5. ATTACK AT DAWN => FYYFHP FY IFBS FYYFHP FY IFBS => ATTACK AT DAWNBy Globules on September 19, 2015 at 4:27 AM
EX1.
#include
int sum(int n)
{
if(n==1)
return 1;
else
return (2*n -1)+sum(n-1);
}
int main()
{
int n;
printf(“Enter the no of odd integer needed\n”);
scanf(“%d”,&n);
printf(“Result = %d\n”,sum(n));
}
if you don’t want to use recursive function then simplest method is
#include
int main()
{
int n;
printf(“Enter the no of odd integer needed\n”);
scanf(“%d”,&n);
printf(“Result = %d\n”,n*n);
}
By Mayur Lokare on October 28, 2015 at 10:23 AM
#include
int main()
{
char str[20];
int i,j,count=1;
printf(“Enter the string\n”);
scanf(“%s”,str);
for(i=0;str[i];i++)
{
for(j=0;j %d\n”,str[i],count);
count=1;
}
}
By Mayur Lokare on October 28, 2015 at 10:23 AM
EX 3.
#include
int main()
{
char str[20];
int i;
printf(“Enter the string”);
scanf(“%[^\n]”,str);
for(i=0;str[i];i++)
{
if(str[i]==’ ‘)
continue;
if((str[i]+5)>90)
str[i] =(str[i]+5-26);
else
str[i] = str[i]+5;
}
printf(“%s\n”,str);
}
By Mayur Lokare on October 28, 2015 at 10:33 AM