4. Partitionen einer Zahl

Partitionen einer Zahl

  • ?

    Hallo ich muss ein programm schreiben, mit dem ich eine beliebige zahl in ihre partitionen teilen kann und die möglichkeiten in eine array speicher.
    Zb die zahl 4
    1 + 1 + 1 + 1
    2 + 1 + 1
    2 + 2
    3 + 1
    4

    ich habe auch den code großteils fertig aber kann mir bitte jemand helfen. Bitte addet mich in icq 628980849

    0
  • G

    fortuner schrieb:

    ich habe auch den code großteils fertig

    Dann zeig doch mal her, was du schon hast. Da kann man dann drauf aufbauen.. hehe

    0
  • ?

    fortuner schrieb:

    ich habe auch den code großteils fertig aber kann mir bitte jemand helfen.

    Wobei?

    fortuner schrieb:

    Bitte addet mich in icq 628980849

    Mit Sicherheit nicht.

    0
  • ?

    using System;

    class PartitionenKanonenAufSpatzen
    {
    static void Main()
    {
    //Einlesen der zu partitionierenden Zahl
    Console.WriteLine("Bitte geben sie eine Zahl ein");
    int eingeleseneZahl= Convert.ToInt32(Console.ReadLine());

    //-----------------Array in Abhängigkeit der eingegebenen Variable erzeugen
    int[] feld = new int [eingeleseneZahl];

    //-----------------Speicher in Abhängigkeit der eingegebenen Variable erzeugen
    // string[] speicher = new string [eingeleseneZahl];

    //Äußere Schleife für die Arrayindizes
    for( int i = eingeleseneZahl-1; i= 0; i--)
    {

    //Schleife um ein einzelnen index die werte 0-9 einzufügen
    for( int y =0; y<eingeleseneZahl;y++)
    {
    int summe=0;

    //Index mit Zahl y(0-eingeleseneZahl) füllen
    feld[i]=y;

    for(int a=0; a<= eingeleseneZahl-1; a++)
    {
    summe= summe + feld[i];
    }

    if( summe== eingeleseneZahl)
    {
    string zeichenkette= "";
    zeichenkette =zeichenkette + feld[i];
    speicher[i]=zeichenkette;
    }

    }
    }

    for (int f = 0; f < eingeleseneZahl; f++)
    {
    Console.WriteLine(feld[f]);
    }
    for ( int b=0; b>eingeleseneZahl;b++)
    { Console.Write(speicher[b]);}
    }
    }

    0
  • ?
     

    using System;

class PartitionenKanonenAufSpatzen
{
static void Main()
{
//Einlesen der zu partitionierenden Zahl
Console.WriteLine("Bitte geben sie eine Zahl ein");
int eingeleseneZahl= Convert.ToInt32(Console.ReadLine());

//-----------------Array in Abhängigkeit der eingegebenen Variable erzeugen
int[] feld = new int [eingeleseneZahl];

//-----------------Speicher in Abhängigkeit der eingegebenen Variable erzeugen
// string[] speicher = new string [eingeleseneZahl];

//Äußere Schleife für die Arrayindizes
for( int i = eingeleseneZahl-1; i= 0; i--)
{

//Schleife um ein einzelnen index die werte 0-9 einzufügen
for( int y =0; y<eingeleseneZahl;y++)
{
int summe=0;

//Index mit Zahl y(0-eingeleseneZahl) füllen
feld[i]=y;

for(int a=0; a<= eingeleseneZahl-1; a++)
{
summe= summe + feld[i];
}

if( summe== eingeleseneZahl)
{
string zeichenkette= "";
zeichenkette =zeichenkette + feld[i];
speicher[i]=zeichenkette;
}

}
}

for (int f = 0; f < eingeleseneZahl; f++)
{
Console.WriteLine(feld[f]);
}
for ( int b=0; b>eingeleseneZahl;b++)
{ Console.Write(speicher[b]);}
}
}
    0
  • V

    Wäre das rekursiv nicht viel einfacher?

    0
  • ?

    wie meinst du, könntest du mir zeigen wie?

    0
  • V

    Fortuner schrieb:

    wie meinst du, könntest du mir zeigen wie?

    War doch nicht einfach. Und ist leider in C++.

    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void part(vector<int>& ergebnis,int rest,int obergrenze){
//als Beispielzahlen nehme ich die Partitionierungen von 4. 
//vector<int> entspricht wohl System.Collections.Generic.List<int>
    if(rest==0){//Wein kein Rest mehjr zu verteilen ist
        for(size_t i=0;i<ergebnis.size();++i)//Liste ausgeben
            cout<<ergebnis[i]<<' ';
        cout<<'\n';
        return;//und fertig, es ist ja kein zu verteilender Rest mehr da. 
    }

    for(int i=rest;i!=0;--i){//die erste zahl kann von 4 bis 1 sein
        ergebnis.push_back(i);//Und die wird hinten an die Liste angefügt
        if(i<=obergrenze)//Ist nur dazu da, soprtierte Ausgabe zu erzwingen, 
//alles Unsortierte wird verworfen
            part(ergebnis,rest-i,min(obergrenze,i));//Und rest-i ist der neue Rest
        ergebnis.pop_back();//i wieder wegmache4n für den nächsten Durchlauf. 
    }
}

int main() {
    vector<int> speicher;
    part(speicher,4,4);
}
    0
  • B

    Mal schnell was zusammengehackt, sicher nicht besonders schön:

    static IEnumerable<int[]> Partitions(int n, int m, List<int> head)
        {
            int min = System.Math.Min(n, m);
            for (int i = 1; i <= min; ++i)
            {
                List<int> newHead = new List<int>(head);
                newHead.Add(i);
                if (n == i)
                    yield return newHead.ToArray();
                else
                    foreach (int[] p in Partitions(n - i, i, newHead))
                        yield return p;
            }
        }

        static IEnumerable<int[]> Partitions(int n)
        {
            return Partitions(n, n, new List<int>());
        }
    0
  • ?

    Das soll der ganze code sein ? bisschen kurz oder?

    Bashar schrieb:

    Mal schnell was zusammengehackt, sicher nicht besonders schön:

    static IEnumerable<int[]> Partitions(int n, int m, List<int> head)
        {
            int min = System.Math.Min(n, m);
            for (int i = 1; i <= min; ++i)
            {
                List<int> newHead = new List<int>(head);
                newHead.Add(i);
                if (n == i)
                    yield return newHead.ToArray();
                else
                    foreach (int[] p in Partitions(n - i, i, newHead))
                        yield return p;
            }
        }

        static IEnumerable<int[]> Partitions(int n)
        {
            return Partitions(n, n, new List<int>());
        }
    0
  • B

    Das ist alles wichtige.

    Es kann höchstens sein, dass das noch ein bisschen zu lang bzw. unelegant ist. Ich hab zuerst was gebastelt, was die geordneten Partitionen zurückgibt. Es sind aber anscheinend die ungeordneten Partitionen gesucht, d.h. dass die Reihenfolge der Summanden keine Rolle spielt und somit 1+2 und 2+1 die gleiche Partition von 3 darstellen. Also hab ich den Code modifiziert und nicht nochmal von vorne gedacht. Kann durchaus sein, dass es besser geht.

    0
  • F

    fortuner schrieb:

    Das soll der ganze code sein ? bisschen kurz oder?

    Hast du den Code denn mal getestet? Nur weil der Code kürzer als deiner ist, heißt es nicht, dass er falsch ist.

    0
  • E

    Der Code von Bashar funktioniert:

    [TestClass]
public class PartitionsSolverTest
{
	[TestMethod]
	public void Partitions_4_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(4, 5));
	}

	[TestMethod]
	public void Partitions_13_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(13, 101));
	}

	[TestMethod]
	public void Partitions_45_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(45, 89134));
	}

	private bool Test(int no, int count)
	{
		var solver = new PartitionsSolver();
		var possibilities = solver.Partitions(no);
		foreach (var possibility in possibilities)
			if (possibility.Sum() != no)
				return false;
		return possibilities.Count() == count;
	}
}

    Alles Grün.

    //Edit: Tests angepasst nach Volkards Liste

    0
  • V

    David W schrieb:

    nur ob die richtige Anzahl von Möglichkeiten ermittelt wird habe ich gerade nicht getestet):

    Das http://oeis.org/A000041 sollten die richtigen Anzahlen sein, vermute ich.

    0
  • E

    Hab die Tests angepasst - thx.

    0
Anmelden zum Antworten