Springen naar inhoud


- - - - -
Solved

Opdracht 067



  • Log in a.u.b. om te beantwoorden
Er zijn 2 reacties in dit onderwerp

#1 josk79

josk79

    Master Developer

  • Leden
  • PipPipPipPipPip
  • 614 berichten
    Laatst bezocht 30 jan 2017 23:38

Geplaatst op 14 oktober 2010 - 21:22

Citeren

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3 7 4
2 4 6
8 5 9 3 That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18.
It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all.
There is an efficient algorithm to solve it.
;o)


#2 josk79

josk79

    Master Developer

  • Leden
  • PipPipPipPipPip
  • 614 berichten
    Laatst bezocht 30 jan 2017 23:38

Geplaatst op 14 oktober 2010 - 21:23

De oplossing voor Project 18 en project 67 zijn iedentiek.

Visual Basic Code:
Option Strict On
Option Infer Off

Module Module1

	Sub main()
		Console.WriteLine("Project 18: " & New Problem018().Solve())
		Console.WriteLine("Project 67: " & New Problem067().Solve())
		Console.ReadKey()
	End Sub



	Public Interface IEulerSolution
		Function Solve() As String
		Event OnDebugMessage(ByVal str As String) 'In plaats van console.writeline dit event raisen
	End Interface


	Public Class Problem018
		Implements IEulerSolution

		Public Event OnDebugMessage(ByVal str As String) Implements IEulerSolution.OnDebugMessage

		Public Function Solve() As String Implements IEulerSolution.Solve

			'Driehoek maken
			Dim triangle As List(Of Integer()) = New List(Of Integer())
			triangle.Add(New Integer() {75})
			triangle.Add(New Integer() {95, 64})
			triangle.Add(New Integer() {17, 47, 82})
			triangle.Add(New Integer() {18, 35, 87, 10})
			triangle.Add(New Integer() {20, 4, 82, 47, 65})
			triangle.Add(New Integer() {19, 1, 23, 75, 3, 34})
			triangle.Add(New Integer() {88, 2, 77, 73, 7, 63, 67})
			triangle.Add(New Integer() {99, 65, 4, 28, 6, 16, 70, 92})
			triangle.Add(New Integer() {41, 41, 26, 56, 83, 40, 80, 70, 33})
			triangle.Add(New Integer() {41, 48, 72, 33, 47, 32, 37, 16, 94, 29})
			triangle.Add(New Integer() {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14})
			triangle.Add(New Integer() {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57})
			triangle.Add(New Integer() {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48})
			triangle.Add(New Integer() {63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31})
			triangle.Add(New Integer() {4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23})

			'Resultaat geven
			Return FindMaximumTotalInTriangle(triangle).ToString

		End Function
	End Class

	Public Class Problem067
		Implements IEulerSolution

		Public InputFilename As String = "c:\triangle.txt"

		Public Event OnDebugMessage(ByVal str As String) Implements IEulerSolution.OnDebugMessage

		Public Function Solve() As String Implements IEulerSolution.Solve
			Dim triangle As List(Of Integer()) = New List(Of Integer())

			'Driehoek uitlezen uit bestand
			Dim infile As System.IO.StreamReader = New System.IO.StreamReader(InputFilename)
			While Not infile.EndOfStream
				Dim rdline As String = infile.ReadLine
				Dim trianglerowstr As String() = rdline.Split(" "c)

				Dim trianglerow(trianglerowstr.Count - 1) As Integer
				For n As Integer = 0 To trianglerowstr.Count - 1
					trianglerow(n) = Integer.Parse(trianglerowstr(n))
				Next
				triangle.Add(trianglerow)
			End While

			'Resultaat geven
			Return FindMaximumTotalInTriangle(triangle).ToString

		End Function
	End Class

	Public Function FindMaximumTotalInTriangle(ByVal Triangle As List(Of Integer())) As Integer
		'Zoek de hoogste waarde door in een driehoek van boven naar beneden
		'door aangrenzende nummers te lopen
		Dim itemcount As Integer = 0
		Dim prevrow As Integer() = {}
		Dim max As Integer = 0

		For Each row As Integer() In Triangle
			Dim sum1, sum2 As Integer
			For i As Integer = 0 To row.Count - 1
				'Bereken de som van het item op deze row + item vorige row (2 mogelijkheden)
				sum1 = If(i > 0, prevrow(i - 1), 0) + row(i)
				sum2 = If(i < row.Count - 1, prevrow(i), 0) + row(i)
				row(i) = Math.Max(sum1, sum2) 'De hoogste waarde van die twee plaatsen op de huidige positie
				max = Math.Max(row(i), max) 'Het hoogste totaal bijhouden (hoeft eigenlijk alleen op laatste regel
			Next
			prevrow = row
		Next

		Return max
	End Function
End Module


edit: Option Infer off toegevoegd (van Vozzie geleerd, Infer kon ik nog niet!)

#3 Vozzie

Vozzie

    Moderator

  • Leden
  • PipPipPipPipPipPipPip
  • 1855 berichten
    Laatst bezocht 12 jul 2017 13:15
Inzender

Geplaatst op 14 oktober 2010 - 22:11

Weeral mooi!

Voor mij is het ok. Iemand zal ze best wel op 1 plaats centraal plaatsen. Of een scriptje daarvoor schrijven :D

Groeten





Ook met taq Solved voorzien

0 gebruiker(s) lezen dit onderwerp

0 lid(leden), 0 bezoeker(s), 0 anonieme gebruikers

Inloggen


[Solved] Untitled 1

Met dank aan J├╝rgen voor de jarenlange inzet van visualbasic.be (anno dec 2000)
Met dank aan Mike en Ronneke voor de jarenlange inzet van vbib.be (anno dec 2010)
Met dank aan PascalBianca voor de jarenlange inzet van vbib.be (anno dec 2016)