Zielwertsuche in einem sortierten Array

3 Lösungen

#342

Fortgeschrittener - C# von JKooP - 21.11.2020 um 09:10 Uhr

Aufgabe 1 (leicht)
In einem beliebig großen sortieren Array soll das erste Vorkommen desjenigen Zahlenpaares per Index ausgegeben werden, bei dem die Summe dem gesuchten Zielwert entspricht.
Dabei kommt jede Zahl nur einmal im Array vor.

arr = [3, 4, 15, 22]
target = 7
Index = [0, 1] (3+4)

arr = [1, 3, 4, 6]
target = 8
Index = [0, 0] oder NULL/Nothing (keine Lösung)

Aufgabe 2 (mittel)
Wie Aufgabe 1, jedoch können Zahlen doppelt vorkommen.

arr = [4, 4, 5, 6]
target = 8
Index = [0, 1] (4+4)

Aufagbe 3 (schwer)
In einem beliebig großen sortieren Array sollen alle Vorkommen derjenigen Zahlenpaare per Indizes ausgegeben werden, bei denen die Summen dem gesuchten Zielwert entsprechen. Dabei können alle Zahlen mehrfach vorkommen.

arr = [1, 3, 4, 6]
target = 7
Indizes = [0, 3] (1+6), [1, 2] (3+4)

Noch ein wenig schwieriger:
arr = [4, 4, 4, 5, 6]
target = 8
Indizes = [0, 1] (4+4), [0, 2] (4 + 4), [1, 2] (4 + 4)

Für alle Aufgaben gilt:
Dopplungen wie [1, 3] und [3, 1] gelten als gleichwertig und sollen nicht ausgegeben werden.

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

1 Kommentar

von Frank (410 Punkte) - 23.02.2021 um 20:01 Uhr

C#-Code

using System;
using System.Collections.Generic;

namespace Zielwertsuche
{
    static class Program
    {
        static void Main()
        {
            int[] list = new int[] { 1, 5, 3, 8, 2, 5, 1, 7, 4, 6, 3, 9, 6, 8, 1, 5, 2 };
            int target = 6;

            List<Tuple<int, int>> pairs = GetListOfPairs(list, target);

            foreach (Tuple<int, int> pair in pairs)
            {
                Console.WriteLine($"indices: {pair.Item1} + {pair.Item2}, Values: {list[pair.Item1]} + {list[pair.Item2]}");
            }
            Console.WriteLine($"number: {pairs.Count}");
        }

        private static List<Tuple<int, int>> GetListOfPairs(int[] list, int target)
        {
            List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();
            for (int i = 0; i < list.Length; i++)
            {
                for (int j = 1; j < list.Length; j++)
                {
                    if (i == j || i < j) break;
                    if (list[i] + list[j] == target)
                    {
                        pairs.Add(new Tuple<int, int>(j, i));
                    }
                }
            }
            return pairs;
        }
    }
}

Kommentare:

JKooP

Punkte: 18090

680 Aufgaben
227 Lösungen
19 Kommentare

05.03.2021 um 18:14 Uhr

Hallo Frank,

für die Zahlen in Deinem (unsortiertem) Array funktioniert der Code natürlich gut, da keine gleichen Zahlen aufeinanderfolgen.
Die Schwierigkeit in der Aufgabe besteht aber darin, dass die Zahlen sortiert sein sollen und gleiche Zahlen beliebig oft hintereinanderstehen können.
Vielleicht fällt Dir dazu auch noch eine Lösung ein.

Viel Spaß weiterhin beim Knobeln.

Gruß Jens

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben

Seite 1 von 1 1