Popcorn Hacks for 3.3
a = 10
b = 40
print ( a + b )
print ( a - b )
print ( a * b )
print ( a / b )
print ( a % b )
50
-30
400
0.25
10
%%javascript
let a = 10;
let b = 40;
console.log(a + b);
console.log(a - b);
console.log(a * b);
console.log(a / b);
console.log(a % b);
<IPython.core.display.Javascript object>
def fibonacc(n):
if n <= 0:
return "invalid"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacc(n - 1) + fibonacc(n - 2)
n = 30
print(f"The {n}th Fibonacci number is: {fibonacc(n)}")
The 30th Fibonacci number is: 514229
%%javascript
function fibonacci(n) {
if (n <= 0) {
return "invalid";
} else if (n === 1) {
return 0;
} else if (n === 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
let n = 30;
console.log(`The ${n}th Fibonacci number is: ${fibonacci(n)}`);
<IPython.core.display.Javascript object>
Homework for 3.3
#Python: Fibonacci Using Matrix Exponentiation
import numpy as np
import logging
import sys
# Configure logging
logging.basicConfig(level=logging.INFO, format='%(levelname)s:%(message)s')
def matrix_multiply(A, B):
"""
Perform matrix multiplication between two numpy arrays A and B.
"""
logging.debug(f"Multiplying matrices:\n{A}\n{B}")
return np.dot(A, B)
def matrix_power(M, power):
"""
Raise matrix M to the specified power using binary exponentiation.
"""
if power < 0:
raise ValueError("Power must be a non-negative integer.")
result = np.identity(len(M), dtype=object)
logging.debug(f"Initial identity matrix:\n{result}")
while power > 0:
if power % 2 == 1:
result = matrix_multiply(result, M)
logging.debug(f"Result after multiplying by M:\n{result}")
M = matrix_multiply(M, M)
logging.debug(f"Matrix M squared:\n{M}")
power = power // 2
logging.debug(f"Power reduced to: {power}")
return result
def fibonacci_matrix(n):
"""
Calculate the nth Fibonacci number using matrix exponentiation.
"""
if not isinstance(n, int):
raise TypeError("Input must be an integer.")
if n < 0:
raise ValueError("Fibonacci number is not defined for negative integers.")
elif n == 0:
return 0
elif n == 1:
return 1
F = np.array([[1, 1],
[1, 0]], dtype=object)
result = matrix_power(F, n-1)
logging.info(f"Matrix raised to power {n-1}:\n{result}")
return result[0][0]
def validate_input(user_input):
"""
Validate the user input to ensure it's a non-negative integer.
"""
try:
value = int(user_input)
if value < 0:
raise ValueError
return value
except ValueError:
raise ValueError("Please enter a valid non-negative integer.")
def main():
"""
Main function to execute the Fibonacci calculation.
"""
try:
user_input = input("Enter the position of the Fibonacci number you want to calculate: ")
n = validate_input(user_input)
fib_n = fibonacci_matrix(n)
print(f"Fibonacci number at position {n} is: {fib_n}")
except ValueError as ve:
logging.error(ve)
except Exception as e:
logging.error(f"An unexpected error occurred: {e}")
sys.exit(1)
if __name__ == "__main__":
main()
INFO:Matrix raised to power 77:
[[8944394323791464 5527939700884757]
[5527939700884757 3416454622906707]]
Fibonacci number at position 78 is: 8944394323791464
%%javascript
2. Java: Fibonacci Using Dynamic Programming
public class FibonacciDP {
// Method to calculate Fibonacci using dynamic programming with optimized space
public static long fibonacci(int n) {
// Base cases for Fibonacci
if (n == 0) return 0;
if (n == 1) return 1;
// Variables to store previous two Fibonacci numbers
long prev1 = 1, prev2 = 0;
long current = 0;
// Iteratively calculate Fibonacci
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
// Efficient matrix exponentiation approach (O(log n))
public static long fibonacciMatrix(int n) {
if (n == 0) return 0;
long[][] F = { { 1, 3 }, { 1, 0 } };
power(F, n - 1);
return F[0][0];
}
// Helper method to perform matrix exponentiation
private static void power(long[][] F, int n) {
if (n == 0 || n == 1) return;
long[][] M = { { 1, 1 }, { 1, 0 } };
power(F, n / 2);
multiply(F, F); // Square the matrix
if (n % 2 != 0) multiply(F, M); // Multiply by M if n is odd
}
// Matrix multiplication helper
private static void multiply(long[][] F, long[][] M) {
long x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
long y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
long z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
long w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
public static void main(String[] args) {
int n = 60;
// Using dynamic programming with optimized space
System.out.println("Fibonacci number at position " + n + " using DP is: " + fibonacci(n));
// Using matrix exponentiation (O(log n))
System.out.println("Fibonacci number at position " + n + " using Matrix Exponentiation is: " + fibonacciMatrix(n));
}
}
<IPython.core.display.Javascript object>
Popcorn Hacks for 3.5
def Hot():
return True # Condition A
def Sunny():
return True # Condition B
# Original statement: if A then B
if Hot():
print("It's hot outside, so it must be sunny", Sunny())
else:
print("It it's not hot outside, it may not be sunny.")
# Contrapositive: if not B then not A
if not Sunny():
print("It's not sunny, so it's not hot.", not Hot())
else:
print("It's sunny outside, but it may not be hot")
It's hot outside, so it must be sunny True
It's sunny outside, but it may not be hot
%%javascript
public class ContrapositiveExample {
public static boolean Hot() {
return true; // Condition A
}
public static boolean Sunny() {
return true; // Condition B
}
public static void main(String[] args) {
// Original statement: if A then B
if (this.Hot()) {
System.out.println("It's hot outside, so it must be sunny" + this.Sunny());
} else {
System.out.println("It it's not hot outside, it may not be sunny.");
}
// Contrapositive: if not B then not A
if (!this.Sunny()) {
System.out.println("It's not sunny, so it's not hot." + !this.Hot());
} else {
System.out.println("It's sunny outside, but it may not be hot");
}
}
}
<IPython.core.display.Javascript object>
Contrapositive Law
The contrapositive of a statement is logically equivalent to the original statement, meaning that both will always have the same truth value. In programming, conditional statements often take the form of logical implications. You can apply the contrapositive logic to simplify, rearrange, or optimize your code structure.
DeMorgan’s Law
This law is a tool that allows a way to simplfiy complex conditions. By implementing this law, the readability of code is much better, since it reduces complexity. Basically, it shows the relatinoship between the AND, OR, and NOT statements.
def check_conditions(a, b):
if not a and not b:
return "Both are False"
else:
return "At least one is True"
a = False
b = False
print(check_conditions(a, b))
Both are False
An example of how to use DeMorgans Law is when you need to compare two statements. For example, saying that its not true someone is tall and athletic can be simplified using DeMorgans by saying that person is not tall OR not athletic.
Homework for 3.5
def AND(Square, Rectangle):
return Square and Rectangle
def OR(Square, Rectangle):
return Square or Rectangle
def NOT(Square):
return not Square
print("Square Rectangle| AND | OR | NOT Square")
print("-------------------------------------------")
for Square in [True, False]:
for Rectangle in [True, False]:
print(f"{Square:<5} {Rectangle:<5} | {AND(Square, Rectangle):<4} | {OR(Square, Rectangle):<3} | {NOT(Square)}")
Square Rectangle| AND | OR | NOT Square
-------------------------------------------
1 1 | 1 | 1 | False
1 0 | 0 | 1 | False
0 1 | 0 | 1 | True
0 0 | 0 | 0 | True
%%javascript
function AND(Square, Rectangle) {
return Square && Rectangle;
}
function OR(Square, Rectangle) {
return Square || Rectangle;
}
function NOT(Square) {
return !Square;
}
console.log("Square Rectangle | AND | OR | NOT Square");
console.log("---------------------------------------------");
let values = [true, false];
values.forEach(Square => {
values.forEach(Rectangle => {
console.log(`${Square} ${Rectangle} | ${AND(Square, Rectangle)} | ${OR(Square, Rectangle)} | ${NOT(Square)}`);
});
});
<IPython.core.display.Javascript object>