Three Homework Problems
September 18, 2015
The n th odd number is 2n−1, so the recursive function counts down from n to zero:
(define (sum-odd n)
(if (zero? n) 0
(+ (sum-odd (- n 1)) n n -1)))
> (sum-odd 5)
25
That’s not tail recursive, so the stack will blow out if n is too large. Here’s a tail-recursive version of the function:
(define (sum-odd-aux n sum)
(if (zero? n) sum
(sum-odd-aux (- n 1) (+ sum n n -1))))
(define (sum-odd n)
(sum-odd-aux n 0))
> (sum-odd 5)
25
If you’re cheeky, you might use a mathematical identity to simplify your solution; no recursion required:
(define (sum-odd n) (* n n))
> (sum-odd 5)
25
The normal way to perform a frequency count of characters in a string is to initialize an array of character counts to zeroes, increment the count of the array position corresponding to the character for each character that is seen, then collect the non-zero counts in the output. That’s a little bit ugly in Scheme, because array access and string access functions have such long names:
(define (freq str)
(let ((counts (make-vector 256 0)))
(do ((i 0 (+ i 1)))
((= i (string-length str)))
(let ((c (char->integer (string-ref str i))))
(vector-set! counts c (+ (vector-ref counts c) 1))))
(do ((i 0 (+ i 1))) ((= 256 i))
(when (positive? (vector-ref counts i))
(display (integer->char i)) (display #\tab)
(display (vector-ref counts i)) (newline)))))
> (freq "hello")
e 1
h 1
l 2
o 1
A more Schemely solution converts the string to a list of characters, sorts them, and collects the non-zero counts; we use the uniq-c function from the Standard Prelude:
(define (freq str)
(uniq-c char=? (sort char<? (string->list str))))
> (freq "hello")
((#\e . 1) (#\h . 1) (#\l . 2) (#\o . 1))
The Caesar cipher uses modular arithmetic to shift letters up and down the alphabet; we replace in-place any upper-case letters and leave everythihg else intact:
(define (caesar n str)
(define (rotate c)
(if (not (char<=? #\A c #\Z)) c
(integer->char (+ (modulo (+ (char->integer c) n -65) 26) 65))))
(list->string (map rotate (string->list str))))
> (caesar 5 "ATTACK AT DAWN")
FYYFHP FY IFBS
> (caesar -5 "FYYFHP FY IFBS")
"ATTACK AT DAWN"
Note that enciphering and deciphering use the same function but negate the shift.
You can run the program at http://ideone.com/MCsvSa.
Programming Praxis 
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 DAWNI 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)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!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 DAWNA 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 DAWNEX1.
#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);
}
#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;
}
}
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);
}