Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды,…
- User
Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде должны быть студенты, обязательно знакомые друг с другом. Круг знакомств задается матрицей (20,20) с элементами
A(ij)={1,если i студент знаком с j
{0,иначе . Вот программа,написанная на языке R. Можешь сделать рефакторинг кодаstudents <- 20 matr=sample(c(0,1), #setting a random matr size=students^2, prob=c(0.1,0.9), #probability of occurrence 0 and 1 replace=T) #with repetitions
team <- function(students, matr=sample(c(0,1), size=students^2, prob=c(0.1,0.9), replace=T)){
set the vector of students
n <- sample(1:students) # write down the numbers from 1 to 20 in different order
reshape vector matr into matrix
know <- matrix(matr, nrow=length(n),ncol=length(n)) #the matrix must be symmetrical
for ( i in 1:nrow(know) ){ # for each student i check symmetry and create symmetric matrix j <- 1 while ( j < i ){ know[i,j] <- know[j,i] j <- j+1 #should be 1 on the diagonal since 1 knows 1, 2 knows the second... } know[i,i] <- 1 } print(know)
include those who know everyone
team_4 <- c() #the students themselves r <- c() #student index
for ( i in 1:length(n) ){ # for each student (select his index from vector n) e <- 0 for ( j in 1:length(n) ){ # calculate the number of students he knows if ( know[n[i],n[j]] == 1 ){ e <- e+1 #if the student knows } } if ( e == length(n) ){ # if he knows everyone -> include in team_4 team_4 <- c(team_4,n[i]) r <- c(r,i) # save the index of student in vector n } }
if ( length(r) != 0 & length(r) == length(n) ){ # all students know everyone
if ( length(n)%%2 == 0 ){ # split on 2 groups equally if n even team_1 <- c(n[1:(length(n)/2)]) team_2 <- c(n[(length(n)/2+1):length(n)]) print(team_1) print(team_2) }else{ # split by 2 groups team_1 <- c(n[1:(length(n)/2+0.5)]) team_2 <- c(n[(length(n)/2+1.5):length(n)]) print(team_1) print(team_2) }}
else{ if ( length(r) != 0 ){ # if we have students who know everyone n <- n[-r] # drop them from the vector n }
# split students into 2 teams vector <- n[-1] team_1 <- c(n[1]) # put the first student from vector n in group 1 as a starting point team_2 <- c() l <- c() u <- 1 while ( (length(team_1)+length(team_2)) < length(n) ){ for ( i in 1:length(team_1) ){ # for each student in team_1 for ( j in 1:length(n) ){ # for students from 1 to 20 e <- 0 if ( is.null(team_2) == FALSE ){ for ( k in 1:length(team_2) ){ if ( n[j] == team_2[k] ){ # if a student already in team_2 , then e = 1 e <- 1 } } } if ( know[team_1[i],n[j]] == 0 & e == 0 ){ # if student i doesn't know the student j and student j not in team 2 -> put student j in team 2 team_2 <- c(team_2,n[j]) if ( length(vector) != 0 ){ for ( k in 1:length(vector) ){ # for each element of the vector, check if student j is equal to it and drop him out of vector if ( vector[k] == n[j] ){ vector <- vector[-k] break # stop when first true } } } } } } o <- c() for ( i in 1:length(team_2) ){ # for each student in team 2 for ( j in 1:length(n) ){ # for all other students e <- 0 for ( k in 1:length(team_1) ){ # check if a user in team 1 if ( n[j] == team_1[k] ){ e <- 1 } } if ( know[team_2[i],n[j]] == 0 & e == 0 ){ # if j and i don't know each other -> put j into team_1 team_1 <- c(team_1,n[j]) o <- c(o,n[j]) # save the number of this student j in vector o if ( length(vector) != 0 ){ for ( k in 1:length(vector) ){ # drop j from vector if ( vector[k] == n[j] ){ vector <- vector[-k] break } } } } } } l <- c(l,length(team_1)+length(team_2)) # save the length of 2 teams if ( u > 1 ){ if ( l[u] == l[u-1] ){ # if the sizes of the teams in 2 consecutive elements are same if ( length(team_1) < length(team_2) ){ team_2 <- c(team_2,vector[1]) # include the first student from vector to team 2 vector <- vector[-1] }else{ team_1 <- c(team_1,vector[1]) # else to team 1 vector <- vector[-1] } } } u <- u+1 } #???????? ?? ???????????? ???????? # double check for relationships of users from team_1 w <- c() if ( length(o) > 0 ){ # o is a vector with students in team1 , who don't know anyone in team 2 and were added in previous step for ( i in 1:length(o) ){ # for each such student check whether he knows anyone of 20 for ( j in 1:length(n) ){ if ( know[o[i],n[j]] == 0 ){ # if no -> create vector w with all students he doesn't know w <- c(w,n[j]) } } } team_2 <- c(team_2,w) # add these users to team_2 } e <- 0 for ( i in 1:length(team_1) ){ # if team_1 and team_2 include the same students -> break -> "?????????? ??????? ?? ??? ??????" for ( j in 1:length(team_2) ){ if ( team_1[i] == team_2[j] ){ e <- 1 break } } if ( e == 1 ){ print("Same students in the teams") break } } if ( e == 0 ){ # if teams are different if ( length(o) != 0 ){ # if vector o with students from team 1 is not 0 team_2 <- team_2[1:(length(team_2)-length(w))] # drop w from team_2 } if ( length(team_1) < length(team_2) ){ # if teams are of different sizeand team 1 is smaller change the order of teams team_3 <- team_1 team_1 <- team_2 team_2 <- team_3 } if ( length(team_4) == 0 ){ # team_4 includes students, who know everyone. If it is 0 then print the teams if ( length(team_1)/length(team_2) <= 2 & length(team_1)/length(team_2) >= 1/2 ){ print(team_1) print(team_2) }else{ print(team_1) print(team_2) print("Everyone doesn't know at least someone: Conditions of task are not satisfied") } }else{ # if team 4 includes some users while ( length(team_4) > 0 & length(team_1) > length(team_2) ){ team_2 <- c(team_2,team_4[1]) # include members of team 4 into team 2 while conditions are true team_4 <- team_4[-1] } if ( length(team_4) != 0 ){ # if we still have some students in team_4 while ( length(team_4) > 0 ){ team_1 <- c(team_1,team_4[1]) # include them in team_1 and team_2 consecutively , start with team 1 team_4 <- team_4[-1] if ( length(team_4) != 0 ){ team_2 <- c(team_2,team_4[1]) team_4 <- team_4[-1] } } print(team_1) # print two teams print(team_2) }else{ # if no students in team_4 -> print teams (again strange part part) if ( length(team_1)/length(team_2) <= 2 & length(team_1)/length(team_2) >= 1/2 ){ print(team_1) print(team_2) }else{ print(team_1) print(team_2) print("At least someone knows everyone: Conditions of task are not satisfied") } } } }} }
team(20)
- Assistant
Код с рефакторингом:
students <- 20 matr <- matrix(sample(c(0,1), students^2, prob=c(0.1,0.9), replace=T), ncol=students)
team <- function(matr){
set the vector of students
n <- sample(1:nrow(matr))
create symmetric matrix
know <- matr know[lower.tri(know)] <- t(know)[lower.tri(know)]
check for students who know everyone
team_4 <- n[rowSums(know) == nrow(know)] r <- match(team_4, n)
remove students who know everyone from the vector n
n <- n[is.na(r)]
split students into 2 teams
team_1 <- n[1] team_2 <- numeric() vector <- n[-1]
while (length(team_1) + length(team_2) < length(n)){ possible_2 <- vector[!(vector %in% c(team_1, team_4, team_2))] # students who are possible to be included in team_2 if(length(possible_2) == 0){ break } for (i in possible_2){ if(all(know[i, team_2] == 1) && range(c(length(team_1), length(team_2)) %/% length(team_1)) <= 2){ team_2 <- c(team_2, i) vector <- vector[!(vector %in% i)] break } } possible_1 <- vector[!(vector %in% c(team_1, team_4, team_2))] # students who are possible to be included in team_1 if(length(possible_1) == 0){ break } for (i in possible_1){ if(all(know[i, team_1] == 1) && range(c(length(team_1), length(team_2)) %/% length(team_2)) <= 2){ team_1 <- c(team_1, i) vector <- vector[!(vector %in% i)] break } } }
if(length(team_4) == 0 && range(c(length(team_1), length(team_2)) %/% length(team_2)) <= 2 && range(c(length(team_1), length(team_2)) %/% length(team_1)) <= 2){ print(team_1) print(team_2) } else{ print("Conditions of task are not satisfied") } }
team(matr)