Προγραμματιστική πρόκληση No 3: Ζάρια

Φτιάξτε μια συνάρτηση που να δίνει ένα ακέραιο τυχαίο αριθμό στο κλειστό διάστημα από 1 έως 100. Οι αριθμοί 1 και 100 θα πρέπει να μπορούν να προκύψουν.

Στην C αυτό είναι εύκολο

#include <stdlib.h>

int rand100() {
     return rand() % 100 + 1
}

Σε άλλες γλώσσες προγραμματισμού είναι εξίσου εύκολο και με λίγο ψάξιμο θα βρεθεί. Αλλά είναι πάντα τόσο απλά τα πράγματα; Είναι ο παραπάνω κώδικας σωστός;

Πρόκληση 1
Χρησιμοποιώντας την συνάρτηση rand100 φτιάξτε ένα ζάρι, δηλαδή τυχαίους αριθμούς από το 1 έως και το 6.

Πρόκληση 2
Αποδείξτε (με κώδικά) ότι το ζάρι που φτιάξατε είναι τίμιο, και κάθε ριξιά έχει ίσες πιθανότητες να προκύψει. Αν δεν είναι προσπαθήστε να φτιάξετε ένα τίμιο ζάρι.

Πρόκληση 3
Φτιάξτε ένα τίμιο ζάρι με n πλευρές, με χρήση της rand100() για οποιαδήποτε τιμή του n .

3 Likes

Δεν πρέπει να χρησιμοποιήσουμε το srand() ?

   The rand() function returns a pseudo-random integer in the range 0 to RAND_MAX inclusive (i.e., the mathemati‐
   cal range [0, RAND_MAX]).

   The srand() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned
   by rand().  These sequences are repeatable by calling srand() with the same seed value.

   If no seed value is provided, the rand() function is automatically seeded with a value of 1.

Δηλαδή με τον τρόπο που το σκέφτομαι (σε c) κάθε φορά που τρέχω το πρόγραμμα είναι σαν σαν ρίχνω μια φορά το ζάρι. Το rand() θα βγάλει έναν αριθμό από τον αλγόριθμό του, εκμεταλεύοντας το seed που αν δεν κάνουμε τίποτα είναι 1. Όταν ξανατρέξω το πρόγραμμα το seed θα είναι πάλι ίδιο και θα βγάζει πάντα τον ίδιο αριθμό.

Για αυτό γράφω στη main: srand(time(NULL)) ώστε το seed να παίρνει διαφορετική τιμή κάθε φορά που τρέχει το πρόγραμμα, από την ώρα του συστήματος (νομίζω ότι είναι σε ακρίβεια δευτερολέπτου, και αν το τρέξω δύο φορές στο ίδιο δευτερόλεπτο, το ζάρι θα βγάλει τον ίδιο αριθμό).

Επομένως:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 1000000

int roll() {
	int value;

	value = rand() % 6 + 1;

	return value;
}

void randomness_check() {
	float clock_start, clock_end, time;
	int random_array[ARRAY_SIZE];
	//int i;
	unsigned long long int i, counter[6];

	clock_start = clock();

	//initialize counter
	for(i = 0; i < 6; i++) {
		counter[i] = 0;
	}
	
	//generate random numbers
	for(i = 0; i < ARRAY_SIZE; i++) {
		random_array[i] = roll();
	}

	//count them
	for(i = 0; i < ARRAY_SIZE; i++) {
		switch(random_array[i]) {
			case 1: {
				counter[0] = counter[0] + 1;
				break;
			}
			case 2: {
				counter[1] = counter[1] + 1;
				break;
			}
			case 3: {
				counter[2] = counter[2] + 1;
				break;
			}
			case 4: {
				counter[3] = counter[3] + 1;
				break;
			}
			case 5: {
				counter[4] = counter[4] + 1;
				break;
			}
			case 6: {
				counter[5] = counter[5] + 1;
				break;
			}
		}
	}

	clock_end = clock();
	time = clock_end - clock_start;
	printf("Calculation took %.2fs\n", time / 1000000);

	printf("1 --> %lld\n", counter[0]);
	printf("2 --> %lld\n", counter[1]);
	printf("3 --> %lld\n", counter[2]);
	printf("4 --> %lld\n", counter[3]);
	printf("5 --> %lld\n", counter[4]);
	printf("6 --> %lld\n", counter[5]);

}

int main(int argc, char *argv[]) {

	srand(time(NULL));

	if (argc == 2) {
		if (*argv[1] == 'r') {
			randomness_check();
		}
	}
	else {
		printf("-->  %d\n", roll());
	}

	return 0;
}

Τρέχοντας ./ονομα_εκτελέσιμου r θα εκτελέσει τον αλγόριθμο δημιουργίας τυχαίου αριθμού 1000000 φορές και θα μετρήσει πόσες φορές παρουσιάστηκαν τα 1,2,…,6. Δηλαδή:

george@george-A715-71G:~$ ./dice r
Calculation took 0.06s
1 --> 166391
2 --> 167603
3 --> 166420
4 --> 166336
5 --> 165860
6 --> 167390

Παρατηρούμε ότι και οι 6 αριθμοί παρουσιάστηκαν 1000000 / 6 φορές περίπου. Το χαρακτηρίζω αρκετά τίμιο. Θεωρητικά όσο περισσότερα “δείγματα” αποκτά τόσο θα μειώνεται το ποσοστό σφάλματος.

Για το n - πλευρο ζάρι:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int roll(int sides) {
	int value;

	value = rand() % sides + 1;

	return value;
}

int main(int argc, char *argv[]) {
	srand(time(NULL));

	if (argc <= 1) {
		printf("Enter the number of sides! ( ./dice <number of sides>)\n");
	}
	else {
		printf("-->  %d\n", roll(atoi(argv[1])));
	}

	return 0;
}
1 Like

Για ξανατρέξε το. Οι αποκλήσεις είναι λίγο μεγάλες. εδιτ (ψέματα, καλές είναι, λίγο οριακές αλλά καλές)

σημείωση δεν το βάζω σαν λύση, απλά για να δούμε πόσο παίρνει στην πάναργη python :wink:

> ipython
Python 3.7.4 (default, Jul 16 2019, 07:12:58) 
Type 'copyright', 'credits' or 'license' for more information
IPython 7.6.1 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from random import randint                                                                                                                                                                                                           

In [2]: def f(): 
   ...:     a = [0]*6 
   ...:     for i in range(10**6): 
   ...:         a[randint(0,5)]+=1 
   ...:     return a 
   ...:                                                                                                                                                                                                                                      

In [3]: time f()                                                                                                                                                                                                                             
CPU times: user 840 ms, sys: 0 ns, total: 840 ms
Wall time: 894 ms
Out[3]: [166868, 166647, 165918, 166974, 166897, 166696]

Και θα βάλω και λίγη υποργρήγορη python :wink:

> ipython --pylab
Python 3.7.4 (default, Jul 16 2019, 07:12:58) 
Type 'copyright', 'credits' or 'license' for more information
IPython 7.6.1 -- An enhanced Interactive Python. Type '?' for help.
Using matplotlib backend: Qt5Agg

In [1]: %time dict(zip(*unique(randint(6,size=10**6), return_counts=True)))                                                                                                                                                                  
CPU times: user 29.7 ms, sys: 0 ns, total: 29.7 ms
Wall time: 37.2 ms
Out[1]: {0: 166459, 1: 166939, 2: 166481, 3: 166803, 4: 166764, 5: 166554}

Τις περισσότερες φορές που το τρέχω βγάζει ένα νούμερο πάνω από 167000. (10^6 / 6 = 166666) Η μέγιστη απόκλιση στο 2 --> 167603 είναι 0,56 % νομίζω, που είναι λίγο ακραίο.

Calculation took 0.03s
1 --> 166267
2 --> 166660
3 --> 166921
4 --> 166957
5 --> 166434
6 --> 166761

Πάντως ο χρόνος εκτέλεσης σε 0.03 sec είναι πιο συνηθισμένος.

ο απλός κανόνας για την εκτίμηση τής αναμενόμενης απόκλισης είναι ν^(1/2) δλδ 166666^(1/2) = 408
έχουμε 167603 - 166666 = 937 δλδ λίγο πάνω από το διπλάσιο. Είναι σημαντική αλλά μέσα στα πλαίσια τού λογικού.

Ευχαριστώ για τις πρώτες συμμετοχές.

Στο παράδειγμα χρησιμοποιείτε μια συνάρτηση που δίνει τιμές από 1..RAND_MAX. Ποια είναι η τιμή τής RAND_MAX; Έχει ζητηθεί όμως να φτιαχτεί τίμιο ζάρι με την rand100, δηλαδή με μια πολύ μικρότερη τιμή, δηλαδή RAND_MAX==100. (Το προσθεσα και στην αρχική δημοσίευση να είναι ποιο σαφές, αν θέλεις δοκίμασε και για οποιαδήποτε τιμή για το RAND_MAX πχ 10).

Αν το καταφέρεις αυτό, θα μπορείς να φτιάξεις ένα πραγματικό τίμιο ζάρι με οποιαδήποτε άλλη τιμή, υπό την προϋπόθεση βέβαια πως έχεις μια καλή γεννήτρια τυχαίων αριθμών για να πατήσεις. Για την ιστορία στον κόσμο της C++ η rand() της C θεωρείτε πολύ κακή επιλογή και συμβουλεύετε η αποφυγή της. Αλλά ας την θεωρήσουμε εδώ σαν μια καλή γεννήτρια.

Αν μιλάς σε μένα δεν το έβαλα για λύση.

Αν κατάλαβα καλά, δηλαδή αντί να κάνω κλήση της rand, θα τη χρησιμοποιώ απλώς έμμεσα από την rand100? Υποτίθεται ότι έχει διαφορά? Το δοκίμασα αλλά βγάζει περισσότερη απόκλιση.

1 Like

Ακριβώς και είναι αναμενόμενο να βγάζει μεγαλύτερη απόκλιση. Άρα βρήκες την διαφορά :grinning:

Γιατί; Ποια είναι η πηγή αυτής της απόκλισης; Πως μπορεί αυτή να εξουδετερωθεί;

Λογικά επειδή με τη rand100, όταν κάνει πηλίκο με 6 στη συνέχεια, (το 6 δεν διαιρεί το 100 ακριβώς αφήνει πηλίκο 4 περιπου, έχουμε και κάτι +1 που με δυσκολεύουν να το σκεφτώ), άρα είναι πιο πιθανό να πάρουμε 1,2,3,4 από το ζάρι από ότι 5,6. Ενώ όταν έχω RAND_MAX μεγαλύτερο αυτό το φαινόμενο είναι μικρότερης σημασίας. Τώρα σκέφτομαι εξουδετέρωση…

edit θα απαντήσω αύριο αν δεν με προλάβει κάποιος, όταν κοιμάμαι το μυαλό λύνει τέτοια προβλήματα

1 Like

Για να εξουδετερώσω αυτό το φαινόμενο, το πιο λογικό μου φαίνεται να αλλάξω το 100 σε ένα πολλαπλάσιο του 6, πχ 60 ώστε όταν κάνω % 6 τα 0,1,2,3,4,5 να τείνουν σε ίδιο ποσό.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 1000000

int rand100() {
     return rand() % 60 + 1;
}

int roll() {
	int value;

	value = rand100() % 6 + 1;

	return value;
}

void randomness_check() {
	float clock_start, clock_end, time;
	int random_array[ARRAY_SIZE];
	unsigned long long int i, counter[6];

	clock_start = clock();

	//initialize counter
	for(i = 0; i < 6; i++) {
		counter[i] = 0;
	}
	
	//generate random numbers
	for(i = 0; i < ARRAY_SIZE; i++) {
		random_array[i] = roll();
	}

	//count them
	for(i = 0; i < ARRAY_SIZE; i++) {
		switch(random_array[i]) {
			case 1: {
				counter[0] = counter[0] + 1;
				break;
			}
			case 2: {
				counter[1] = counter[1] + 1;
				break;
			}
			case 3: {
				counter[2] = counter[2] + 1;
				break;
			}
			case 4: {
				counter[3] = counter[3] + 1;
				break;
			}
			case 5: {
				counter[4] = counter[4] + 1;
				break;
			}
			case 6: {
				counter[5] = counter[5] + 1;
				break;
			}
		}
	}

	clock_end = clock();
	time = clock_end - clock_start;
	printf("Calculation took %.2fs\n", time / 1000000);

	printf("1 --> %lld\n", counter[0]);
	printf("2 --> %lld\n", counter[1]);
	printf("3 --> %lld\n", counter[2]);
	printf("4 --> %lld\n", counter[3]);
	printf("5 --> %lld\n", counter[4]);
	printf("6 --> %lld\n", counter[5]);

}

int main(int argc, char *argv[]) {

	srand(time(NULL));

	if (argc == 2) {
		if (*argv[1] == 'r') {
			randomness_check();
		}
	}
	else {
		printf("-->  %d\n", roll());
	}

	return 0;
}

Τώρα από το 100 έχει σίγουρα λιγότερη απόκλιση, ίσως και από πριν βάλω την rand100:

george@george-A715-71G:~$ ./exe r
Calculation took 0.03s
1 --> 166301
2 --> 167015
3 --> 166448
4 --> 166665
5 --> 166879
6 --> 166692

edit: Αναγνωρίζοντας αυτό το πρόβλημα και αφού googlara, θα μπορούσαμε στη συνάρτηση rand100 να απορρίπτουμε εξαρχής τις τιμές από το RAND_MAX που προκαλούν άνιση κατανομή, αλλά έτσι έχω τροποποιήσει τη rand100 και ξεφεύγω από τις προδιαγραφές:

int rand100() {
	int value;

	while(1) {
		value = rand();
		if (value < RAND_MAX - RAND_MAX % 60) {
			return value % 60;
		}
	}
}

Επανέρχομαι για διευκρινήσεις. Ας πούμε πως έχουμε ένα φυσικό ζάρι με αριθμούς από 1 έως 6, ή από 0 έως 5 όπως θα έπρεπε να είναι ένα κανονικό ζάρι :grinning:

  • Πες πως θέλεις να φτιάξεις τους αριθμούς 1 και 2 μπορείς; Βεβαίως. Θα ρίξεις το ζάρι και αν το αποτέλεσμα είναι μονός αριθμός θα πάρεις το 1 αλλιώς το 2. Θα είναι το αποτέλεσμα τίμιο;

  • Έστω τώρα πως θέλεις τους αριθμούς 1,2,3,4. Μπορείς; Βεβαίως! Αν βγάλει τους αριθμούς 5,6 θα το αγνοήσω εντελώς. Θα είναι το αποτέλεσμα τίμιο;

  • Έστω τώρα πως θέλεις να φτιάξεις τους αριθμούς από 1 έως 11. Μπορείς; Βεβαίως. Θα ρίξεις το ζάρι δυο φορές. Θα τα αθροίσεις και θα πάρεις τους αριθμούς από δυο έως 12. Θα είναι το αποτέλεσμα τίμιο;

  • Ας επιστρέψουμε στο παράδειγμα 2. Σε κώδικα θα γράφαμε κάτι σαν rand6() % 4 όπου η συνάρτηση rand6() είναι το ζάρι με πολύ μικρή τιμή για το RAND_MAX ίση με το 5 ή 6). Δίνει τώρα αυτός ο τύπος ένα τίμιο ζάρι;

Οπότε το ερώτημα που πρέπει να απαντηθεί πρώτα είναι πόσα τίμια ζάρια (και πως) μπορούν να φτιαχτούν από ένα τίμιο ζάρι με 6 πλευρές.

1 Like

Να παραθέσω κι εγώ την εργασία μου… :slight_smile: Dice

import random
'''
Info: Roll a dice

Author: Christos Stm
Last modified: October 2019
'''

class Dice(object):
    ''' Δημιουργεί ένα αντικείμενο τύπου 'Ζάρι' και χειρίζεται την μέθοδο τυχαίας ρίψης και της τυχαίας κατανομής
    αποτελεσμάτων εάν και εφόσον κληθούν...'''
    the_dice_sides = {} # Λεξικό αποθήκευσης αποτελεσμάτων αν κληθεί η allocation_of_resaults
    def __init__(self, sides=6):
        self.sides = sides
        # for i in range(1, self.sides+1):
        #     Dice.the_dice_sides[i]=0

    def allocation_of_results(self, tries):
        ''' Μέθοδος που ελέγχει την ίση κατανομή των αποτελεσμάτων για n προσπάθειες'''
        Dice.the_dice_sides = {} # Αδειάζω το λεξικό σε περίπτωση που έχει ξαναχρησιμοποιηθεί
        for i in range(tries):
            # Για κάθε μια απ' τις προσπάθειες που περνάμε ως όρισμα,
            resault = self.roll() # παίρνουμε μια τυχαία ρίψη ζαριού
            Dice.the_dice_sides[resault] = Dice.the_dice_sides.get(resault, 0) + 1 # Αποθήκευση του αποτελέσματος στο λεξικό
        for i in sorted(Dice.the_dice_sides):
            print(i, Dice.the_dice_sides[i])
    def roll(self):
        ''' Μέθοδος τυχαίας ρίψης ζαριού '''
        return random.randint(1, self.sides)
    def __str__(self):
        return str('Dice Side: ' + str(self.roll()))

def game():
    while True:
        start = input('Do you want to start?\nType (S)tart or (E)xit ~: ').strip()
        if start.upper()[0] == 'E': break
        elif start.upper()[0] == 'S':
            while True:
                play = input('\nIf do you want to play once, press Enter\nElse, type a number of tries\n'
                             'For "exit" type (E)xit~: ')

                if not play:
                    while True:
                        sides = input('Dice Sides: ')
                        if sides.isdigit():
                            roll = Dice(int(sides)) # Δημιουργία και ρίψη ζαριού με n πλευρές
                            print(roll)
                            break
                        else: continue
                elif play.upper()[0] == 'E': break
                elif play.isdigit():
                    while True:
                        sides = input('Dice Sides: ')
                        if sides.isdigit():
                            roll = Dice(int(sides)) # Δημιουργία και ρίψη ζαριού με n πλευρές
                            number = int(play)
                            roll.allocation_of_results(number) # κλήση της μεθόδου allocation πάνω στο ζάρι
                            break
                        else: continue
                else: continue
        else: continue

if __name__=='__main__':game()
2 Likes

Καλώς ήρθες @ChristosStm στην παρέα μας.

1 Like

Καλώς σας βρήκα! Την καλησπέρα μου κι από εδώ! :slight_smile:

1 Like

Εγώ πάλι βλέπω ένα σχετικά τίμιο ζάρι όσο έχουμε αύξηση του αριθμού των ρίψεων

#!/usr/bin/env python
import random
# Αρχικοποίηση ζαριού
rolls = {"1":0, "2":0, "3":0, "4":0, "5":0 ,"6":0}
# Ερώτηση για αριθμό ρίψεων
n=int(input("Δώσε αριθμό ρίψεων : "))

# Ρίψη ζαρίας
for i in range(1,n+1):
    roll=random.randint(1,6)
    rolls[str(roll)]+=1

# Στατιστικά ζαριάς
for k in range (1,7):
    percentage=100*rolls[str(k)]/sum(rolls.values())
    print("Το",k,"ήρθε",rolls[str(k)],f"φορές με πιθανότητα {percentage:.2f}","%")

Ας πούμε σε ένα μεγάλο αριθμό ρίψεων μου έβγαλε

Δώσε αριθμό ρίψεων : 1235435
Το 1 ήρθε 205859 φορές με πιθανότητα 16.66 %
Το 2 ήρθε 205667 φορές με πιθανότητα 16.65 %
Το 3 ήρθε 205835 φορές με πιθανότητα 16.66 %
Το 4 ήρθε 206116 φορές με πιθανότητα 16.68 %
Το 5 ήρθε 205240 φορές με πιθανότητα 16.61 %
Το 6 ήρθε 206718 φορές με πιθανότητα 16.73 %

Που είναι σχετικά fair. Επιπλέον πρέπει να συνυπολογισθεί το γεγονός ότι αν ο αριθμός ρίψεων δεν είναι ακριβώς διαιρούμενος με το 6 τότε κάποια ζαριά θα ευνοηθεί.

1 Like

Και λόγω της μεγάλης τιμής του RANDMAX είναι αρκετά τίμιο.

Η πρόκληση όμως δεν είναι να φτιάξεις ένα τίμιο ζάρι με την χρήση της έτοιμης συνάρτησης roll=random.randint(1,6), αλλά να το φτιάξεις από το rand100. Σε κώδικα κάπως έτσι

temp = random.randint(1,100)
roll = .... temp ...

Με άλλα λόγια πες πως ΔΕΝ έχεις την randint έτοιμη και φτιαγμένη από κάποιον άλλον. Σου έχω δώσει εγώ μια άλλη, που όμως δίνει τιμές μέχρι το 100.

def rand100:
    return  random.randint(1,100)

και πουθενά αλλού στον κώδικα δεν θα πρέπει να υπάρχει άμεση κλίση της randint

Επομένως οτιδήποτε ΔΕΝ είναι μέχρι το 6 δεν μπαίνει στο dictionary και δεν προσμετράται και λογικά αυτό επιδρά στην “τιμιότητα” του ζαριού.

Αυτό ναι είναι όντως πρόκληση

σιγά την πρόκληση, ενδεικτικά:

def zari():
    while True:
        x = randint(1,100)
        if x < 7: return x

:stuck_out_tongue:

3 Likes

Και επιτέλους έχουμε την πρώτη λύση που απαντά στο πρόβλημα. Και δουλεύει. Βέβαια αν δούλευες κάπου και το παρουσίαζες αυτό σαν λύση θα έπρεπε κανονικά να σε μαστιγώσουν και να σε πετάξουν στους κροκόδειλους, αλλά μέχρι στιγμής έχουμε την καλύτερη απάντηση.

Είσαι βέβαιος όμως πως αυτό που θα προκύψει είναι τίμιο, η θα πρέπει να αναλάβουν και οι αρκούδες;