Write a single-resource sequential program in SR that reads two positive integers from the keyboard and then prints on the screen all prime numbers between the two input numbers (inclusive).
For example, if the numbers 5 and 15 are input, then your program will print
5 7 11 13
Errors to check for are if the second number input is less than the first number input and if any input number is negative.
Given a positive integer N, write a program that computes a quantity regarding the solution of x**2 + y**2 = z**2 where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x is less than or equal to y and such that x, y, and z are relatively prime, i.e., have no common divisor larger than 1.
The Input
The input consists of a sequence of positive integers, one per line. Each integer in the input will be less than or equal to 1,000.
The Output
For each integer N in the input, print the number of relatively prime triples (such that each component of the triple is less than or equal to N).
Sample Input
10 25 100Sample Output
1 4 16 158
Write an SR program that does the following. The input contains a series of lines. The output contains the lines rotated 90 degrees clockwise.
Sample input:
now is the time
Sample output:
tin hso e w t i m e
This problem involves determining, for a group of gift-giving friends, how much more each person gives than they receive (and vice versa for those that view gift-giving with cynicism).
In this problem each person sets aside some money for gift-giving and divides this money evenly among all those to whom gifts are given.
However, in any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.
Given a group of friends, given the money each person in the group spends on gifts, and given a (sub)list of friends to whom each person gives gifts, write an SR program that determines how much more (or less) each person in the group gives than they receive. First write a single resource SR program, then rewrite your program so that it has two or more resources.
The Input
The input is a sequence of gift-giving groups. A group consists of several lines:
All names are lower-case letters, there are no more than 10 people in a group, and no name is more than 12 characters in length. Money is a non-negative integer less than 2000 dollars. The input consists of one or more groups.
The Output
For each group of gift-givers, the name of each person in the group should be printed on a line followed by the net gain (or loss) received (or spent) by the person. Names in a group should be printed in the same order in which they first appear in the input.
The output for each group should be separated from other groups by a blank line. All gifts are integers. Each person gives the same integer amount of money to each friend to whom any money is given, and gives as much as possible. Any money not given is kept and is part of a person's ``net worth'' printed in the output.
Sample Input
5 dave laura owen vick amy dave 200 3 laura owen vick owen 500 1 dave amy 150 2 vick owen laura 0 2 amy vick vick 0 0 3 liz steve dave liz 30 1 steve steve 55 2 liz dave dave 0 2 steve liz
Sample Output
dave 302 laura 66 owen -359 vick 141 amy -150 liz -3 steve -24 dave 27
Truth in lending.
Back before the days of truth in lending, banks and finance companies used a system called ``simple interest.'' With this system, to get the monthly payment Pm, the stated annual interest rate Iy was multiplied by the term n (in years) and the result multiplied by the principal Pv. This was then added to the principal and the result divided by the number of payments (usually monthly):
Pv + Iy x n x Pv
Pm = -----------------
12 x n
For example, a $3000 loan for 3 years, at 6 2/3 %, would have a monthly
payment of $100.00.
Under truth in lending, the monthly payment Pm is calculated by the following formula:
Ip x Pv
Pm = --------------------
1 - ( 1 + Ip )**(-m)
where Ip is the (monthly) periodic interest rate, Pv is the principal,
and m is the number of payments. A $3000 loan, with $100 monthly
payments, for 36 months, has a monthly interest rate of 1.0208% or an
annual percentage rate of 12.25%,
0.010208 x 3000
100 = -------------------
1 - 1.010208**(-36)
not 6 2/3 %, hence the ``Truth in Lending'' law.
Write a program to calculate the annual percentage rate given the principal, the ``simple interest,'' the term, and the number of payments per year. Since it is difficult to obtain a closed-form solution for the true periodic interest rate i from the above equation, try an iterative approach.
Sample input:
3000 6.66667 3 12 3600 5 3 12
Sample output:
PRINCIPAL = 3000.00 SIMPLE_INTEREST = 6.67 TERM = 3.0 Number of Periods per Year = 12 PAYMENT = 100.00 ANNUAL PERCENTAGE RATE = 12.25 PRINCIPAL = 3600.00 SIMPLE_INTEREST = 5.00 TERM = 3.0 Number of Periods per Year = 12 PAYMENT = 115.00 ANNUAL PERCENTAGE RATE = 9.31
Unidirectional TSP
Background
Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) --- finding whether all the cities in a salesperson's route can be visited exactly once with a specified limit on travel time --- is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check.
This problem deals with finding a minimal path through a grid of points while traveling only from left to right.
The Problem
Given an m x n matrix of integers, write an SR program
that computes a path of minimal weight. A path starts anywhere
in column 1 (the first column) and consists of a sequence of steps
terminating in column n (the last column). A step consists of
traveling from column i to column i+1 in an adjacent (horizontal or
diagonal) row. The first and last rows (rows 1 and m) of a matrix
are considered adjacent, i.e., the matrix ``wraps'' so that it represents
a horizontal cylinder. Legal steps are illustrated below.
The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.
For example, two slightly different 5 x 6
matrices are shown below (the only difference is the numbers in the bottom
row).
The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
The Sample Input Format
The sample input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by m x n integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in a sample input file.
For each specification the number of rows will be between 1 and 9 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.
The Sample Output Format
Two lines have been output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest has been be output.
Sample Input
5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 8 6 4 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 2 2 9 10 9 10
Sample Output
1 2 3 4 4 5 16 1 2 1 5 4 5 11 1 1 19
Hint: think about working backwards. A 5 20 matrix takes forever using the brute-force left-to-right recursive algorithm, whereas the right- to-left backwards optimal method returns instantly.