Rekursive Lösung in JavaScript

[Camping_RIDER]

Aloha ;)

Ich hatte die selbe Idee zur Rekursion wie @1unitedpower, war aber zu faul mir über eine echt funktionale Implementierung Gedanken zu machen und habe JavaScript bemüht.

/**
 * returns an array of the k-1 numbers remaining in the following process: 
 * take numbers from 1 to n and continuously count out each k-th number,
 * begin counting at startnumber
 *
 * @param n quantity of numbers to select from
 * @param k index-distance between removed numbers
 * @param startnumber first number to count, defaults to 1
 * @returns array of remaining numbers or undefined if the parameters are not well defined
 */
function findRemainingNumbers(n, k, startnumber) {
    // n is a positive integer
    if (!Number.isInteger(n) || n <= 0) return undefined;

    // k is an integer and can not be less than 2
    if (!Number.isInteger(k) || k < 2) return undefined;
    
    // provide default value for startnumber
    if (startnumber === undefined) startnumber = 1;

    // startnumber has to be a valid integer inside of 1..n
    if (!Number.isInteger(startnumber) || n < startnumber || startnumber < 1) return undefined;

    // create array with numbers
    let elements = [];
    for (let i = 1; i <= n; i++) { elements.push(i); }

    // delegate to universal function
    // if the numbers until startnumber shall not be counted, counting starts at 1 - startnumber
    // e.g. if the number 3 shall be counted as first, the countoffset has to be -2
    const countoffset = 1 - startnumber;
    return findRemainingElements(elements, k, countoffset);
}

/**
 * continuously count out the k-th element from the given elements
 * until there are not more than k-1 left 
 * and return the remaining elements
 *
 * @param elements array of elements to work on
 * @param k index-distance between removed elements
 * @param countoffset where to start counting - first element is counted as countoffset + 1
 * @returns array of remaining elements or undefined if the parameters are not well defined
 */
function findRemainingElements(elements, k, countoffset) {
    // elements must be an array
    if (!Array.isArray(elements)) return undefined;

    // k is an integer and can not be less than 2
    if (!Number.isInteger(k) || k < 2) return undefined;

    // provide default value for countoffset
    if (countoffset === undefined) countoffset = 0;

    // countoffset is an integer
    if (!Number.isInteger(countoffset)) return undefined;

    // only do something if there are more than k elements
    if (elements.length < k) return elements;

    // choose by counting for one iteration
    let remainingElements = elements.filter(
        // keep elements where the counted number is less than one
        // keep elements where the counted number is not divisible by k
        // the counted number equals to the sum of index and countoffset plus 1
        (_, index) => index + countoffset + 1 < 1 || (index + countoffset + 1) % k != 0
    );

    // calculate where to start counting in the next iteration:
    // for the last element in the array, the counted number is
    // lastIndex + countOffset + 1, and because lastIndex + 1 equals elements.length
    // the offset for the next count is elements.length + countoffset
    const nextoffset = elements.length + countoffset;

    // do next iterations
    return findRemainingElements(remainingElements, k, nextoffset);
}

Wenn man sich die Prüfung der Variablen auf Typ und sinnvollen Wertebereich spart kann man das sogar in einen noch einigermaßen überschaubaren Einzeiler packen - der Rekursion sei Dank:

function findRemainingElements(elements, k, countoffset) {
  return elements.length < k ? elements : findRemainingElements(elements.filter((_, index) => index + countoffset + 1 < 1 || (index + countoffset + 1) % k != 0), k, elements.length + countoffset);
}

Zu Aufgabenteil c hab ich zwei Lösungsansätze formuliert - einer induktiv, der andere deduktiv:

var positions = {};
for (let i = 1; i <= 1000; i++) {
	positions[i+''] = 0;
}
for (let i = 1; i <= 1000; i++) {
	let nrs = findRemainingNumbers(1000,3,i);
	positions[nrs[0]+'']++;
    positions[nrs[1]+'']++;
}
console.log(positions);

Ergibt ein Objekt mit 1000 Einträgen, die jeweils 2 sind. Demnach sind bei variablem Startpunkt alle Positionen gleich wahrscheinlich.

Das lässt sich auch logisch begründen. Das Verschieben des Startpunkts um x nach rechts entspricht dem Verschieben aller Werte um x nach links bei gleichbleibendem Startpunkt. Dann ist aber nach 1000-x Verschiebungen genau die ursprüngliche Anordnung erreicht, es werden also genau dieselben Verschiebungen durch den Algorithmus gejagt, nur in einer anderen Reihenfolge.

Da der Algorithmus nicht von der Reihenfolge seiner Aufrufe abhängt muss die Wahrscheinlichkeit daher vom Startpunkt unabhängig sein.

Die Aufgabenstellung hat mich übrigens an meine Vorlesungen „Einführung in die Programmierung“ und „Paradigmen der Programmierung“ erinnert.

Die Übungsblätter dazu habe ich echt genossen; eine Lösung zu programmiertechnischen Problemen zu finden ist eine Aufgabe mit sehr selbstbelohnendem Charakter.

So viel Genugtuung wie ein gelöstes Programmierproblem hat mir ein selbst geglückter Beweis eines mathematischen Satzes noch nie bereitet.

Grüße,

RIDER