Die Mathe-Redaktion - 18.11.2017 03:38 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 249 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » (*) C++-Puzzle
Druckversion
Druckversion
Antworten
Antworten
Autor
Schule (*) C++-Puzzle
nullptr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 30
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-08-21


Wie lautet die Ausgabe vom folgenden C++-Programm?
C++
#include <iostream>
 
typedef unsigned long long num;
 
int main(void) {
    num n = 42, k = 0;
 
    for (num i = 1; i <= (1ULL << n); ++i) {
        num j = i;
        while (j > 0) {
            ++k;
            j = j % 2 ? j - 1 : j / 2;
        }
    }
 
    std::cout << k << std::endl;
 
    return 0;
}

Lösungen können direkt veröffentlicht werden.

Viel Spaß!



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-08-21


n       End   f(n)
1	2	3
2	4	9
3	8	26
4	16	71
5	32	184
6	64	457
7	128	1098
8	256	2571
9	512	5900


Differenz-Folge: 6,17,45,113,273,641,1473,3329
 3*2^k*k + 5*2^k + 1
Offsetverschiebung:
 3*2^(k-2)*(k-2) + 5*2^(k-2) + 1  ,k=1...8

sum 3*2^(k-2)*(k-2) + 5*2^(k-2) + 1,k=1...n
= 3*2^(n - 1)*n + n-2*(2^n - 1)
Offsetverschiebung 2:

f(n)=3*2^(n - 1)*n + n-2*(2^n - 1)+1

f(42)=268280837177389
das gesuchte Ergebnis



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2017-08-22


Und hier die Laufzeitabschätzung des langsamen Algorithmus mit exponentiellem Anstieg:

per Iterationsrechner ergibt:
i      n=aB[i]  max [s]                 min [s]            
0	26      4.467618     		4.3938113
1	27      8.963368     		8.9304404
2	28      18.09195     		18.151158
3	29      36.73038     		36.892308
4	30      74.99007     		74.983775
5	31      153.9356     		152.40484
6	32      317.6551     		309.76351
7	33      658.8434     		629.59567
8	34      1373.255     		1279.6559
9	35      2876.075     		2600.9061
10	36      6051.589     		5286.3530
11	37      12790.95     		10744.535
12	38      27154.84     		21838.314
13	39      57896.52     		44386.468
14	40      123956.9     		90215.688
15	41      266475.1     		183363.77
16	42      575131.72=6.6Tage      	372687.667=4.3Tage
17	43      1246124.45		757489.291
18	44      2710190.9=31 Tage     	1539600.253

Hätte also 4...7 Tage gedauert.
Mit der expliziten Formel könnte man hingegen in ms alles berechnen!



  Profil  Quote  Link auf diesen Beitrag Link
nullptr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 30
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2017-08-22


Glückwunsch, du hast die Lösung gefunden!

Die explizite Formel habe ich auch verwendet.

Gibt außerdem einen recht einfachen Zusammenhang zwischen der Binärdarstellung von j und der Anzahl der Schleifendurchläufe der while-Schleife. Bei p Einsen und q Nullen sind das 2p + q - 1 Durchläufe.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
stupidix
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.09.2017
Mitteilungen: 7
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-09-05


Nun ja, das Programm zählt die Anzahl der 1-Bits in sämtlichen 42-stelligen Binärzahlen zusammen (1) und addiert dann noch die Position des jeweils höchstwertigsten Bits drauf (2) und macht dasselbe schlußendlich noch für die dreiundvierzigstellige Zahl 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000.

Zu (1): Es gibt 2^42 solche Zahlen mit je 42 Ziffern.  Die Hälfte der Ziffern sind Nullen, die anden sind Einsen.

Zu (2): 2^41 Zahlen beginnen mit 1.  2^40 Zahlen beginnen mit 01.  2^39 Zahlen beginnen mit 001 usw.

Zu (3): Für diese Zahl ist für (1) noch +1 auf die Summe zu Rechnen und für (2) nochmal + 42.

Also gibt das Programm aus (mit n := 42):

  2^n * n / 2
+ Summe von i = 0, ..., n-1 (i * 2^i)
+ 1 + n
= 268280837177389

--

Einfacher geschrieben:
    num k = (1ULL << n) * n / 2 + 1 + n;
    for (num i = 0; i < n; i++)
        k += i * (1ULL << i);



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 

 AQA

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]