Joseph’s ring (Joseph’s problem) is a mathematical application problem: given n people (numbered 1,2,3… Sit around a round table. Count off the number of k, count up to m of the person out; His next man counted off from 1, and the man who had counted to M stepped out again; Repeat this pattern until everyone around the round table is out of line. For example, if there are 5 people, the number of the person numbered as 1 begins to count, the number of the person numbered as 3 goes out, and the number of the person numbered as 4 at the end.

Write a function for the total number of people 50, starting with the number of 1, counting to 3 out of the column, calculate the last person out of the column number.

NSUInteger printLastDequeuedNumberInRoundTable(NSUInteger allMembersCount, NSUInteger dequeueNumber) { NSMutableDictionary<NSNumber *, NSString *> *dictM = @{}.mutableCopy; NSUInteger startIdx = 1; //first idx is 1in round table issue
    //all members always dequeued finally
    while(dictM.allKeys.count ! = allMembersCount) { //members always sing from `1.. dequeueNumber`for (NSUInteger i = 1; i <= dequeueNumber; i++) {
            //member at startIdx dequeued
            if (dictM[@(startIdx)]) {
                //ignore this, step next
                i--;
            } else {
                if (i == dequeueNumber) {
                    //record every `round table number` when last member who sing `dequeueNumber`
                    dictM[@(startIdx)] = @"dequeued";
                    if (dictM.allKeys.count == allMembersCount) {
                        NSUInteger lastNum = (startIdx - 1)%allMembersCount + 1;
                        NSLog(@"last member at number %ld dequeued", lastNum);
                        return lastNum;
                    } else {
                        NSLog(@"member at number %ld dequeued", (startIdx - 1)%allMembersCount + 1);
                    }
                }
            }
            ++startIdx;
            //the index inround table member varied from 1 to allMembersCount startIdx = (startIdx - 1)%allMembersCount + 1; }}return NSNotFound;
}
Copy the code

The results of

NSUInteger lastNumber = printLastDequeuedNumberInRoundTable(50, 3);
lastNumber = 11;
Copy the code