Problem Solving Algorithms PDF

Problem #1 Design an algorithm: pseudocode or flowchart... Given two integers, x and n, compute x raised to the n-th power. Use only simple math: +, -, *, /. Problem #1 Design an algorithm: pseudocode or flowchart... Given two integers, x and n, compute x raised to the n-th power. Use only simple...

Problem #1 Design an algorithm: pseudocode or flowchart... Given two integers, x and n, compute x raised to the n-th power. Use only simple math: +, -, *, /. Problem #1 Design an algorithm: pseudocode or flowchart... Given two integers, x and n, compute x raised to the n-th power. Use only simple math: +, -, *, /. Did you assume n > 0? Why? Integers can be negative, zero, or positive. When in doubt, ask. (Or if you can’t ask, state your assumptions.)  n is any integer Example solutions: x: base (integer) n: exponent (integer) assuming n ≥ 0 r: result (floating-point) x: base (integer) n: exponent (non-neg integer) r ←1 // answer if n is 0 r: result (integer) if n ≥ 0 for i from 1 to n r ←1 // answer if n is 0 r ←r * x for i from 1 to n end r ←r * x else end for i from 1 to (-n) r ←r / x end end Problem #2 Design an algorithm: pseudocode or flowchart... Given an integer, funds, that represents an amount of money ($$), determine the smallest number of bills ($10, $5, $1) needed.  code-like design Example solution: funds: total dollars (integer) high-level design tens, fives, ones: counters (integer) funds: total dollars (integer) tens, fives, ones: counters (integer) tmp ← funds tens, fives, ones ← 0 tmp ← funds while tmp ≥ 10 subtract $10 until tmp < 10, count each time tens ← tens + 1 subtract $5 until tmp < 5, count each time tmp ← tmp - 10 remainder is the number of ones end while tmp ≥ 5 fives ← fives + 1 tmp ← tmp - 5 end ones ← tmp  Example solution: recognizing that repeated subtraction is division funds: total dollars (integer) tens, fives, ones: counters (integer) tmp ← funds tens ← tmp / 10 // integer division, throws away remainder tmp ← tmp - tens * 10 fives ← tmp / 5 tmp ← tmp - fives * 5 ones ← tmp Problem #3 Design an algorithm: pseudocode or flowchart... Given an integer, x, assumed to be a perfect square, find the 𝑥 positive square root of x.  Example solution: Idea: compute squares until you match the target x: perfect square (integer) s: square root (integer) This can take a lot of steps for large x. s ←1 Can you think of a faster way? while s*s < x s ←s + 1 end Summary: Problem Solving Make sure you understand the problem. Determine what data is given or is needed. Ask for clarifications, or state your assumptions. Think about how data will be transformed. What do you know about the data? What operations can be performed, and what will they do? What operations will get you closer to the desired result? Consider these programming structures: Sequential Draw a picture/flowchart Conditional Write some pseudocode Iterative Types of Data C Representation Inside the CPU Integer 123 binary 0xab10 (2's comp) Floating-point 12.34 binary 0.999 (IEEE fl pt) Literals 123. 2.3e44 8e-6 Text 'a' binary "abc" (ASCII) Integer Numbers Decimal Hexadecimal Octal 123 0x123 0123 0xabc 0xABC 0XaBc What about negative integers? What about binary notation? Variables To create a variable, declare it. type name ; Compiler allocates a memory location to hold the variable’s value. The type of a variable indicates what kind of value can be stored, and what operations can be performed on this value. The type of a variable determines how much memory is required. Variables To create a variable, declare it. Rules for name: type name ; letters, digits, underscore cannot begin with a digit up to 31 characters Native C types: int integer Names are case-sensitive. double floating-point Avoid starting with underscore. float floating-point char character Variables Declaring an integer variable... int numBoxes; // number of boxes in the truck this is a comment, ignored by the compiler until the end of line Variables When you declare a variable, you may initialize it. int numBoxes = 20; this allocates the variable and stores a specific value in its memory address Variables To change the value of a variable, use an assignment statement. numBoxes = 30; this changes the value stored in an already-declared variable This is an expression. (Next slide...) Match the type of the variable being assigned. This must be a variable name. Look, no type! This is how you know it’s an assignment and not a declaration. Expression Specifies a value. Any combination of... Examples Literal 123 0xabc Variable numBoxes total_weight Operator applied to numBoxes + 1 literal/variable total_weight + numBoxes * 20 Arithmetic (integer) int a = 9 int b = 5; Operator Meaning Example Value - (unary) Change sign -a -9 + Add a + b 14 - Subtract a - b 4 discards * Multiply a * b 45 fractional result / Divide a / b 1 Modulo % (remainder) a % b 4 remainder of division Precedence When multiple operators act on the same operand... a*b+c/3-1 ((a*b)+(c/3))-1 Math: C arithmetic operators: P - parentheses P - parentheses E - exponentiation U - unary M - multiplication M - multiplication, division, modulo D - division A - addition, subtraction A - addition S - subtraction Lots of other operators, but this is a good start. Simple sequential program Just declarations and assignments. funds: total dollars int funds = 78; tens, fives, ones: counters int tmp = funds; int tens; tmp ← funds int fives; tens ← tmp / 10 int ones; tmp ← tmp - tens * 10 tens = tmp / 10; // how many 10s? fives ← tmp / 5 tmp = tmp % 10; // left over? tmp ← tmp - fives * 5 fives = tmp / 5; // how many 5s? ones ← tmp ones = tmp % 5; // left over? Print a string #include printf("Hello, world. It’s 2024.\n"); This is a special notation for a linefeed character. Just one character is printed. This is a literal string. The quotation marks are not included in the string. They mark the beginning and end. This is a function provided by the C standard library. Its job is to print a string to the “standard output stream.” Print an #include integer expression printf("%d", funds); This is an expression that specifies the value to be printed. This is a conversion code. It says that an integer value must be provided, and it will be printed using decimal notation. This is a literal string. The quotation marks are not included in the string. They mark the beginning and end. This is a function provided by the C standard library. Its job is to print a string to the “standard output stream.” Print a string with #include embedded integer values printf("%d dollars: %d 10s, %d 5s, %d 1s\n", funds, tens, fives, ones); Each conversion code must have a matching value (expression) of the proper type. Use %x to print an integer value using hexadecimal notation. Read an integer value #include scanf("%d", &funds); This is a variable where the input value will be stored. It must be preceded by a “magical” ampersand. This is a conversion code. It says that characters from the input stream will be read and interpreted as a decimal integer value. This is a literal string. The quotation marks are not included in the string. They mark the beginning and end. This is a function provided by the C standard library. Its job is to read values from the “standard input stream.”  Don’t forget the magical ampersand! scanf("%d", &funds); For now, just read one value per scanf. scanf never prints anything. Only put conversion codes in the string. DO NOT put other characters in the string. When your program reaches scanf, it will wait until the user types something (and hits Enter). Prompt and read #include printf("Enter a dollar amount: "); scanf("%d", &funds); Printing and reading are separate. Typically, will print a prompt message to let the user know what to do. printf("Enter a dollar amount: "); fflush(stdout); scanf("%d", &funds); Sometimes we need this, to make sure output appears before the program waits on input. int main() { int funds; // Total Amount int tmp; // Temporary Processing Value int tens; // Number of $10 int fives; // Number of $5 int ones; // Number of $1 printf("Enter a dollar amount: "); // Information for User scanf("%d", &funds); // Entry of total amount of money tmp = funds; // Set tmp equal to funds entered tens = tmp / 10; // how many 10s? tmp = tmp % 10; // left over? fives = tmp / 5; // how many 5s? ones = tmp % 5; // left over? // Output information to the user printf("$%d: %d 10s, %d 5s, and %d 1s\n“, funds, tens, fives, ones); return 0; }