1
해결하려는 문제는 이와 같습니다. 나는 나에게 숫자의 범위를 말하고, N를 제공하고 있습니다여러 가지 그룹 번호에서 2 개의 숫자를 선택하는 방법에 대한 C# 해결책
는 0, 1, ..., N-2, N-1입니다.
나는 쌍이 주어져서 그 숫자 쌍이 동일한 "그룹"에 있음을 알립니다.
예 :
N=6, 0 및 1이, 짝 1 및 4의 관계가 설정 및 2 및 3가 쌍으로, 그리고 나머지 숫자가 자신의 그룹에있는 것을 알고있다.
그럼 그룹화는 {0, 1, 4}, {2, 3}, {5}입니다.
이 그룹들 중 다른 그룹에서 두 개의 숫자를 선택하는 방법은 11이며 이것이 내가 풀려고하는 숫자입니다. 이 선택 사항은 다음과 같습니다
{0,2}, {0,3}, {0,5}, {1,2}, {1,3}, {1,5}, {4,2}, {4,3}, {4,5}, {2,5}, {3,5}
사람이 어디 알아내는 데 도움이 수 있습니까 논리가 잘못 되었나요? 왜냐하면 나는 더 큰 테스트 케이스에 실패하고 더 작은 테스트 케이스를 통과시키기 때문이다.
내 코드 : 예를 들어
static int Combinations(int N, int K)
{
decimal result = 1;
for (int i = 1; i <= K; i++)
{
result *= N - (K - i);
result /= i;
}
return (int)result;
}
/// <summary>
/// Given a set of n numbers 0, 1, ..., n-1 and a list of pairs
/// of the numbers from the set where each pair (i,j) means that
/// number i and j are in the same group, find the number of ways
/// to choose 2 numbers that are not in the same group.
/// </summary>
static int PoliticallyCorrectPairs(int n, Tuple<int, int>[] pairs)
{
// Create a map that from each number to a number representing
// the group that it is in. For example, if n = 5 and
// pairs = { (0, 1), (2, 3), (0, 4) }, then the map will look
// like
// 0 -> 1
// 1 -> 1
// 2 -> 2
// 3 -> 2
// 4 -> 1
// indicating that 0,1,4 belong to one group and 2,3 to the other.
int[] gmap = new int[n];
int k = 1;
foreach(Tuple<int, int> pair in pairs)
{
int i = pair.Item1,
j = pair.Item2;
// If both i and j are already in groups, combine those into a
// single group if it isn't already.
if (gmap[i] != 0 && gmap[j] != 0)
{
if(gmap[i] != gmap[j])
{
for(int m = 0; m < n; ++m)
if(gmap[m] == gmap[j])
gmap[m] = gmap[i];
}
}
else if(gmap[j] != 0) // j is in a group and i isn't
gmap[i] = gmap[j]; // add i to j's group
else if(gmap[i] != 0) // i is in a group and j isn't
gmap[j] = gmap[i]; // add j to i's group
else
gmap[i] = gmap[j] = k++; // Put both in same new group.
}
// Those not assigned to a group each end up in a group alone.
for(int i = 0; i < gmap.Length; ++i)
if(gmap[i] == 0)
gmap[i] = k++;
// Get the group sizes as an array.
int[] gcnts = gmap.GroupBy(x => x).Select(g => g.Count()).ToArray();
// Total number of ways to choose pairs of numbers.
int totalCombinations = Combinations(n, 2);
// Number of pairs from previous count that are in the same group.
int impossibleCombinations = gmap.GroupBy(x => x)
.Select(g => g.Count())
.Where(count => count > 1)
.Sum(count => Combinations(count, 2));
return totalCombinations - impossibleCombinations;
}
, 내가
[TestMethod]
public void Sample1()
{
int N = 5;
Tuple<int, int>[] pairs = new Tuple<int, int>[]
{
Tuple.Create(0, 1),
Tuple.Create(2, 3),
Tuple.Create(0, 4)
};
Assert.AreEqual(6, PoliticallyCorrectPairs(N, pairs));
}
을 전달하지만
[TestMethod]
public void TestCase2()
{
int N = 100;
Tuple<int, int>[] pairs =
@"0 11
2 4
2 95
3 48
4 85
4 95
5 67
5 83
5 42
6 76
9 31
9 22
9 55
10 61
10 38
11 96
11 41
12 60
12 69
14 80
14 99
14 46
15 42
15 75
16 87
16 71
18 99
18 44
19 26
19 59
19 60
20 89
21 69
22 96
22 60
23 88
24 73
27 29
30 32
31 62
32 71
33 43
33 47
35 51
35 75
37 89
37 95
38 83
39 53
41 84
42 76
44 85
45 47
46 65
47 49
47 94
50 55
51 99
53 99
56 78
66 99
71 78
73 98
76 88
78 97
80 90
83 95
85 92
88 99
88 94"
.Split('\n')
.Select(line =>
{
int[] twofer = line.Split(' ').Select(s => int.Parse(s)).ToArray();
return Tuple.Create(twofer[0], twofer[1]);
})
.ToArray();
Assert.AreEqual(3984, PoliticallyCorrectPairs(N, pairs));
}
내가 잘못 갈거야 어떤 생각을 실패입니까?
'I는 0과 1은 같은 그룹에 있는지 알의 말합시다'--- 그 이유는 무엇입니까? 서로 다른 그룹에서 두 개의 숫자를 선택하는 방법의 수는 11입니다 --- 왜? –
@LeiYang 방금 코드 주석을 읽는다면 의미가 있습니다. 그는 몇 곳에서 설명을 엉망으로 만들었습니다. – Slepz
@Slepz는 괜찮지 만, OP가 실제 단어 사용자 스토리를 더 잘 표현할 수 있습니다. –