Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Vampirzahlen (Selektionen)

Eine Vampirzahl ist eine natürliche Zahl mit gerader Anzahl von Ziffern, die sich in zwei gleichlange Faktoren zersetzen lässt, die zusammengenommen eine Permutation der Ausgangszahl ergeben, wobei die beiden Faktoren nicht gleichzeitig auf 0 enden dürfen. Die Faktoren nennt man die »Eckzähne« (englisch fangs) einer Vampirzahl.


Beispiel:

Die kleinste Vampirzahl ist 1260, mit den Eckzähnen 21 und 60, da 21 × 60 = 1260 und 21_60 eine Ziffernpermutation von 1260 ist.


Aufgabe:

Schreibe eine Routine, die prüft, ob eine Zahl eine Vampirzahl ist. Finde anhand dieser Routine:


  1. die 5., 10. und 15. Vampirzahl
  2. die kleinste Vampirzahl, die mehr als zwei Eckzähne hat


Gib jede Vampirzahl zusammen mit ihren Eckzähnen aus. Dokumentiere außerdem die Kalkultationszeiten deines Programms.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

4 Lösung(en)

/*	Update 14.01.2023:
	Lösung ohne Permutation -> nochmals Halbierung der Zeiten!
	C++ 20 | GCC
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath> // sqrt, log10 (GCC)

inline const auto get_vampire_numbers(size_t max) {
	std::map<size_t, std::vector<std::tuple<size_t, size_t>>> out{};
	max = size_t(sqrt(max));
	for (size_t left{ 10 }; left < max; ++left) {
		for (size_t right{ left + 1 }; right < max; ++right) {
			if (int(log10(left)) != int(log10(right)) || left % 10 == 0 && right % 10 == 0) continue;
			const auto pro{ left * right };
			if ((int(log10(pro)) + 1) & 1) continue;
			auto pro_str{ std::to_string(pro) };
			auto lr_str{ std::to_string(left) + std::to_string(right) };
			std::sort(pro_str.begin(), pro_str.end());
			std::sort(lr_str.begin(), lr_str.end());
			if (pro_str == lr_str) out[pro].push_back({ left, right });
		}
	}
	return out;
}

int main() {
	const auto vn{ get_vampire_numbers(1'000'000) };

	// Aufgabe 1 (bestimmte Vampirzahlen)
	const auto get_vn{ [&vn](const size_t& num) { return vn.size() < num ? 0 : std::next(vn.begin(), num - 1)->first; } };
	std::cout << "5. Vampirzahl: " << get_vn(5) << "\n";
	std::cout << "10. Vampirzahl: " << get_vn(10) << "\n";
	std::cout << "15. Vampirzahl: " << get_vn(15) << "\n";

	// Aufgabe 2 (erste mit mehr als 2 Eckzähnen)
	const auto find{ std::find_if(vn.begin(), vn.end(), [](const auto& i) {return i.second.size() > 1; }) };
	if (find != vn.end()) std::cout << "\nmehr als 2 Eckzaehne: " << find->first << "\n\n";

	// Aufgabe 3 (alle Vampirzahlen aus einem bestimmten Bereich)
	auto i{ 0 };
	for (const auto& num : vn) {
		std::cout << ++i << ". " << num.first << ": ";
		for (const auto& [left, right] : num.second) // C++ 20!
			std::cout << left << " x " << right << "   ";
		std::cout << "\n";
	}
}
                

Lösung von: Jens Kelm (@JKooP)

# Ein bisschen angelehnt an die interessante Lösung in C++
def vampires():
  import math, itertools, bisect, collections
  def count_digits(num):
    ret = 10 * [0]
    while num:
      num, rem = divmod(num, 10)
      ret[rem] += 1
    return ret
  for factor_digit_len in itertools.count(1):
    results = collections.defaultdict(lambda: [])
    factor_range = range(10**(factor_digit_len-1)+1, 10**factor_digit_len) # 2 to 9, 11 to 99, 101 to 999, ...
    for left_factor in factor_range: # for example with 101 to 999, 101 cannot be smaller, because 100*999 will not have 6 digits
      # find the minimum right factor, so that the product has double the amount of the factor digits
      right_factor_start_index = bisect.bisect_left(factor_range, 2*factor_digit_len, key=lambda n: int(math.log10(left_factor*n))+1)
      if right_factor_start_index == len(factor_range):
        # there is no such right factor, so skip
        continue
      # the maximum right factor is left_factor, so we avoid checking duplicates (when the left and right factors are swapped)
      for right_factor in range(factor_range[right_factor_start_index], left_factor+1):
        if left_factor % 10 == right_factor % 10 == 0:
          continue
        product = left_factor * right_factor
        product_digits = count_digits(product)
        left_digits, right_digits = count_digits(left_factor), count_digits(right_factor)
        # product is permutation, if it has the same amount of each digit as the left_factor and right_factor added
        if all((p == s for p, s in zip(product_digits, (l+r for l, r in zip(left_digits, right_digits))))):
          if left_factor != right_factor:
            results[product].extend((left_factor, right_factor))
          else:
            results[product].append(left_factor)
    yield from sorted(results.items(), key=lambda x: x[0])

found_smallest = False
for i, (n, v) in enumerate(vampires(), start=1):
  vamp_str = f"{n} mit Eckzähnen {', '.join(map(str, v))}"
  print(f"{i}. Vampirzahl: {vamp_str}")
  if len(v) > 2 and not found_smallest:
    print(f"Kleinste Vampirzahl mit mehr als zwei Eckzähnen: {vamp_str}")
    found_smallest = True
  if i == 155: # 939658 with factors 986, 953
    # it takes 2.79 seconds to get the first 155 vampire numbers until 939658
    break
                

Lösung von: Name nicht veröffentlicht

Number.prototype.getDivisors = function() {
  let out = [], i;
  for (i = 1; i <= Math.ceil(this/2); i++)
    if (this % i == 0) out.push(i);
  return out;
}

Number.prototype.getLength = function() { return this.toString().length; }

function isPermutation(a, b) {
  return (
    a.toString().split('').sort().join('') ==
    b.toString().split('').sort().join('')
  );
}

function hasCommonDigits(long, short) {
  long = long.toString(); short = short.toString();
  for (let i = 0; i < short.length; i++)
    if (long.indexOf(short[i]) == -1) return false;
  return true;
}

/* /!\ FREILICH NUR ALS AKTUELLER STAND DER ARBEIT ZU VERSTEHEN /!\
   vor allem fehlt noch eine zuverlässige methode, um zahlen
   von vornherein auszuschließen. */
function vanHelsingTest(num) {
  let out = {
    coffin: num,
    result: false,
    fangs: []
  }
  // ungerade anzahl von ziffern? vade retro!
  if (num.getLength() % 2 != 0) return out;
  // teiler: nur halbe länge und mögliche ziffern
  let divs = num.getDivisors().filter(function(x) {
    return (x.getLength() == num.getLength() / 2) && (hasCommonDigits(num, x));
  });
  // teiler aneinanderhalten
  for (let i = 0; i < divs.length; i++)
    for (let j = i+1; j < divs.length; j++) {
      if (
        divs[i] * divs[j] == num &&
        isPermutation(num, '' + divs[i] + divs[j]) &&
        // beide divisoren dürfen nicht auf 0 enden
        !(divs[i] % 10 == 0 && divs[j] % 10 == 0)
      ) out.fangs.push([divs[i], divs[j]]);
    }
  // hat eckzähne = vampir!
  if (out.fangs.length != 0) out.result = true;
  return out;
}

// vampirzahl mit fängen ausgeben
function exposeToSunlightml(corpse) {
  let out = `<b>${corpse.coffin.toLocaleString()}</b> `;
  if (!corpse.result) out += 'ne estas vampira.';
  else for (let i of corpse.fangs)
    out += ` = ${i.join(' × ')}`;
  return out;
}

/********\
|* MAIN *|
\********/

// genereller speedtest
let tests = [
  12,             //        1 ms
  1234,           //        2 ms
  123456,         //       15 ms
  12345678,       //    1.218 ms
  1234567890      //  117.516 ms
  //123456789012  //  ab hier wird's ein geduldspiel
];
for (let i of tests) {
  console.time();
  console.log( vanHelsingTest(i) );
  console.timeEnd();
}

// zur aufgabe;
let theCount = 1000,
    found15 = false, belaLugosisDead = false,
    hallOfHeads = [];

console.time();
for (theCount; !(found15 && belaLugosisDead); theCount++) {
  // keine zahl mit ungerader anzahl an ziffern!
  if (theCount.getLength() % 2 != 0) theCount *= 10;
  let suspect = vanHelsingTest(theCount);
  if (suspect.result) hallOfHeads.push(suspect);
  if (hallOfHeads.length == 15) found15 = true;
  if (suspect.fangs.length > 1) belaLugosisDead = true;
}
console.timeEnd(); // in etwa die zeit um ein ei zu kochen :(
                   // »Hmm.. lecker gekochtes ei!« (DeNiro, »Angel Heart«)

// ausgabe
for (theCount = 0; theCount < hallOfHeads.length; theCount++)
  switch (true) {
    case (theCount == 5-1):
    case (theCount == 10-1):
    case (theCount == 15-1):
      document.write(`
        <p>La ${theCount+1}<sup>a</sup> vampirnombro:</br>
        ${exposeToSunlightml(hallOfHeads[theCount])}</p>
      `);
    break;
    case (hallOfHeads[theCount].fangs.length > 1):
      document.write(`
        <p>L’unua vampirnombro kun pli ol 2 ?irdentoj:</br>
        ${exposeToSunlightml(hallOfHeads[theCount])}</p>
      `);
  }

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// NET 7.x | C# 11.x | VS-2022
static SortedDictionary<uint, List<(uint, uint)>> GetVampireNumbers(uint max) {
    var out_ = new SortedDictionary<uint, List<(uint, uint)>>();
    max = (uint)Math.Sqrt(max);
    for (uint left = 10; left < max; ++left) {
        for (uint right = left + 1; right < max; ++right) {
            if ((int)Math.Log10(left) != (int)Math.Log10(right) || left % 10 == 0 && right % 10 == 0) continue;
            var pro = left * right;
            if (((int)Math.Log10(pro) + 1) % 2 != 0) continue;
            if (pro.ToString().OrderBy(x => x).SequenceEqual((left.ToString() + right.ToString()).OrderBy(x => x)))
                if (out_.TryGetValue(pro, out List<(uint, uint)>? value))
                    value.Add((left, right));
                else
                    out_.Add(pro, new List<(uint, uint)> { (left, right) });
        }
    }
    return out_;
}
var vn = GetVampireNumbers(1_000_000); // 206 ms

// Aufgabe 1 (bestimmte Vampirzahlen)
new List<uint> { 5, 10, 15 }.ForEach(x => Console.WriteLine($"{x}. Vampirzahl: {vn.Skip((int)x - 1).FirstOrDefault().Key}"));

// Aufgabe 2 (erste mit mehr als 2 Eckzähnen)
Console.WriteLine($"\nmehr als 2 Eckzähne: {vn.Where(x => x.Value.Count > 1).FirstOrDefault().Key}\n");

// Aufgabe 3 (alle aus einem bestimmten Bereich)
var i = 0;
foreach (var num in vn)
{
    Console.Write($"{++i}. {num.Key}: ");
    foreach (var (left, right) in num.Value)
        Console.Write($"{left} x {right}    ");
    Console.WriteLine();
}
                

Lösung von: Jens Kelm (@JKooP)

Verifikation/Checksumme:

  1. 1827, 105210, 115672
  2. 125460

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1.5
Schwierigkeit: Mittel
Webcode: tyyu-5ni7
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen