Last active
October 9, 2022 02:55
-
-
Save minghao912/d2dc5933222b760f880e5276fd582fb1 to your computer and use it in GitHub Desktop.
Math 170E HW 2 Question 6
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* First, compile the program using clang or gcc | |
* Then, run the program using: ./hw2_better <value of N> <number of runs> <print? T/F=1/0> | |
* Output is in the file 'out.data', with each run on its own line | |
* --- | |
* Example run: ./hw2_better 20 1 1 will run the program once with N=20, printing out the | |
* contents of the handshake array (how many times each pair of students shook hands) | |
* | |
* Example output: | |
* 0 1 2 3 4 | |
* ------------------------------ | |
* 0 1 4 5 6 | |
* 1 4 5 5 | |
* 2 5 5 | |
* 3 7 | |
* | |
* It took 47 handshakes for all students to shake hands. | |
* Students 3 and 4 shook hands the most times, at 7 handshakes. | |
**/ | |
#include <time.h> | |
#include <stdlib.h> | |
#include <stdio.h> | |
#define DEFAULT_N 20 | |
#define DEFAULT_RUNS 100 | |
int allShookHands(unsigned int** const handshakeArray, int classSize) { | |
for(unsigned int i = 0; i < classSize - 1; i++) { | |
for(unsigned int j = i + 1; j < classSize; j++) { | |
if (handshakeArray[i][j] == 0) | |
return 0; | |
} | |
} | |
return 1; | |
} | |
long long run(int n, int print) { | |
// Data structures | |
long long numHandshakes = 0; | |
unsigned int** handshakeArray = (unsigned int**) calloc(n - 1, sizeof(unsigned int*)); | |
for (unsigned int i = 0; i < n - 1; i++) { | |
handshakeArray[i] = (unsigned int*) calloc(n, sizeof(unsigned int)); | |
} | |
while(!allShookHands(handshakeArray, n)) { | |
// Random pair of students | |
int studentA = 0, studentB = 0; | |
while(studentA == studentB) { // Should not shake hands with self | |
studentA = rand() % n; | |
studentB = rand() % n; | |
} | |
// Ensure studentB > studentA | |
if (studentB < studentA) { | |
int temp = studentA; | |
studentA = studentB; | |
studentB = temp; | |
} | |
// Record handshakes | |
handshakeArray[studentA][studentB] += 1; | |
// Increase hadnshake count | |
numHandshakes++; | |
} | |
if (print) { | |
// Table header | |
printf("\t"); | |
for (unsigned int i = 0; i < n; i++) { | |
printf("%6d", i); | |
} | |
printf("\n\t"); | |
for (unsigned int i = 0; i < (6 * n); i++) { | |
printf("-"); | |
} | |
printf("\n"); | |
// Table contents | |
unsigned int maxHandshakes = 0; | |
unsigned int maxPair[2] = {0}; | |
for (unsigned int i = 0; i < n - 1; i++) { | |
printf("%d\t", i); | |
for (unsigned int j = 0; j < n; j++) { | |
if (j <= i) { | |
printf("%s", " "); | |
continue; | |
} | |
printf("%6d", handshakeArray[i][j]); | |
// Set max | |
if (handshakeArray[i][j] > maxHandshakes) { | |
maxHandshakes = handshakeArray[i][j]; | |
maxPair[0] = i; | |
maxPair[1] = j; | |
} | |
} | |
printf("\n"); | |
} | |
// Summary | |
printf("\n"); | |
printf("It took %lld handshakes for all students to shake hands.\n", numHandshakes); | |
printf("Students %d and %d shook hands the most times, at %d handshakes.\n", maxPair[0], maxPair[1], maxHandshakes); | |
} | |
// Ending stuff | |
for (int i = 0; i < n - 1; i++) { | |
free(handshakeArray[i]); | |
} | |
free(handshakeArray); | |
return numHandshakes; | |
} | |
int main(int argc, char** argv) { | |
// Initialize random function | |
srand(time(NULL)); | |
// Take in CLI args | |
// First: # for N | |
// Second: # of runs | |
// Third: print handshake array? T/F | |
int n = DEFAULT_N; | |
int runs = DEFAULT_RUNS; | |
int print = 0; | |
if (argc >= 3) { | |
sscanf(argv[1], "%d", &n); | |
sscanf(argv[2], "%d", &runs); | |
} | |
if (argc == 4) { | |
sscanf(argv[3], "%d", &print); | |
} | |
// Store results | |
long long* results = (long long*) calloc(runs, sizeof(long long)); | |
for (int i = 0; i < runs; i++) { | |
results[i] = run(n, print); | |
} | |
// Write results | |
FILE *f = fopen("out.data", "wb"); | |
for (int i = 0; i < runs; i++) { | |
fprintf(f, "%lld\n", results[i]); | |
} | |
fclose(f); | |
// Ending stuff | |
free(results); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <time.h> | |
#include <stdlib.h> | |
#include <stdio.h> | |
#define N 20 | |
#define RUNS 100 | |
int allShookHands(const int handshakeArray[N][N], int classSize) { | |
for(int i = 0; i < classSize; i++) { | |
for(int j = 0; j < classSize; j++) { | |
if (handshakeArray[i][j] == 0) | |
return 0; | |
} | |
} | |
return 1; | |
} | |
long long run() { | |
// Data structures | |
long long numHandshakes = 0; | |
int handshakeArray[N][N] = {0}; | |
while(!allShookHands(handshakeArray, N)) { | |
// Random pair of students | |
int studentA = rand() % N; | |
int studentB = rand() % N; | |
// Record handshakes | |
handshakeArray[studentA][studentB] = 1; | |
// Increase hadnshake count | |
numHandshakes++; | |
} | |
return numHandshakes; | |
} | |
void main(int argc, int** argv) { | |
// Initialize random function | |
srand(time(NULL)); | |
// Store results | |
long long results[RUNS] = {0}; | |
for (int i = 0; i < RUNS; i++) { | |
results[i] = run(); | |
} | |
// Write results | |
FILE *f = fopen("out.data", "wb"); | |
for (int i = 0; i < RUNS; i++) { | |
fprintf(f, "%lld\n", results[i]); | |
} | |
fclose(f); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment