Created
September 21, 2024 10:03
-
-
Save AlbertoMonteiro/565cea0d6d99f4c46f5030fd39bd4177 to your computer and use it in GitHub Desktop.
2005. Subtree Removal Game with Fibonacci Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using Spectre.Console; | |
| for (var i = 10; i >= 1; i--) | |
| { | |
| AnsiConsole.MarkupLine($"Dado que n é igual a [yellow]{i:00}[/] então [blue]Alice[/] {(FibonacciTree.DoAliceWins(i) ? "[green]vence[/]" : "[red]perde[/]")}"); | |
| } | |
| public record Node(int Value, Node? Left = null, Node? Rigth = null) | |
| { | |
| public static explicit operator int(Node node) | |
| => node.Value; | |
| public static Node operator +(Node a, Node b) | |
| => new(a.Value + b.Value, a.Value == b.Value ? null : b, a); | |
| } | |
| public class FibonacciTree | |
| { | |
| public static bool DoAliceWins(int n) | |
| => Fibonacci(n).totalNodes % 2 == 0; | |
| public static (Node rootNode, int totalNodes) Fibonacci(int value) | |
| { | |
| var totalNodes = 1; | |
| Node a = new(1); | |
| var b = a; | |
| for (int i = 1; i < value; i++) | |
| { | |
| var newNode = a + b; | |
| totalNodes++; | |
| if (a.Left is not null) | |
| totalNodes++; | |
| if (a.Rigth is not null) | |
| totalNodes++; | |
| b = a; | |
| a = newNode; | |
| } | |
| return (a, totalNodes); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment