星期五, 4月 27, 2012

求出n取k組合的列表 Objective-C 版

這是本灌水系列最後一篇,到此已練功完成。
如果有其他語言需要解答,我找到這裡有各種不同的程式語言版本(缺Objective-C XD);此站看來是學生作業的好幫手呀。

以下是特別版的code:
#import <Foundation/Foundation.h>

@interface Combinations : NSObject
{
    NSMutableArray *list;
}

-(NSMutableArray *) calc: (int) all andWant: (int) want;
-(void) calc: (NSMutableArray *) before andAll: (int) all andWant: (int) want;
-(void) addList:(NSMutableArray *) before andAfter: (NSMutableArray *) after;
@end

@implementation Combinations

-(void) addList:(NSMutableArray *)before andAfter:(NSMutableArray *)after {
    NSMutableArray *temp= [NSMutableArray arrayWithArray:before];
    [temp addObjectsFromArray:after];
    [list addObject:temp];
}

-(void) calc:(NSMutableArray *) before andAll: (int) all andWant:(int)want {
    NSMutableArray *temp= [[NSMutableArray alloc] init];
    if(want == 0)
    {
        for(int i=0; i<all;i++)
        {
            [temp addObject:  @"0"];
        }
        [self addList: before andAfter: temp];
    }
    else if(all == want) {
        for(int i=0; i<all;i++)
        {
            [temp addObject: @"1"];
        }
        
        [self addList: before andAfter: temp];
    }
    else if(all == 1)
    {
        switch(want)
        {
                NSString *k =  [NSString stringWithFormat:@"%d", want];
                [temp addObject:k];
        }
        [self addList: before andAfter: temp];
    }
    else
    {
        NSMutableArray *newbefore=[NSMutableArray
                                   arrayWithArray:before];
        
        [newbefore addObject:@"0"];
        [self calc:  newbefore andAll: all-1 andWant: want];
        
        NSMutableArray *newbefore2=[NSMutableArray
                                    arrayWithArray:before];
        [newbefore2 addObject:@"1"];
        [self calc:  newbefore2 andAll: all-1 andWant: want-1];
    }
}

-(NSMutableArray *) calc :(int)all andWant :(int)want {
    list =[[NSMutableArray alloc]init];
    NSMutableArray *temp = [[NSMutableArray alloc] initWithObjects:
                            nil];
    [self calc:temp andAll:all andWant:want];
    return list;
}
@end

int main(int argc, const char * argv[])
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    Combinations *cb = [Combinations alloc];
    int all=4;
    int want=2;
    if(argc == 3)
    {
        all = atoi(argv[1]);
        want = atoi(argv[2]);
    }
    NSMutableArray *arr=[cb calc :all andWant:want];
    printf("\n%d取%d,結果共%lu個\n", all, want, arr.count);
    for(int i=0; i<arr.count; i++) {
        NSMutableArray *temp =[arr objectAtIndex:i];
        for(int j=0; j<temp.count; j++) {
            printf("%s ",  [[temp objectAtIndex:j] UTF8String]);
        }
        puts("");
    }
    [cb release];
    [pool drain];
    return 0;
}

以下是一般的組合版本
#import <Foundation/Foundation.h>
#import <Foundation/NSArray.h>

@interface Combinations : NSObject
{
    NSMutableArray *list;
}

-(NSMutableArray *) calc: (int) all andWant: (int) want;
-(void)calc: (NSMutableArray *) before andInlist:(NSMutableArray *) inlist andAll: (int) all andWant: (int) want;

-(void) addList:(NSMutableArray *) thelist ;
-(void) addList:(NSMutableArray *) before andAfter: (NSMutableArray *) after;
@end

@implementation Combinations

-(void) addList:(NSMutableArray *) thelist{
    [list addObject:thelist];
}

-(void) addList:(NSMutableArray *)before andAfter:(NSMutableArray *)after {
    NSMutableArray *temp= [NSMutableArray arrayWithArray:before];
    [temp addObjectsFromArray:after];
    [list addObject:temp];
}

-(void) calc:(NSMutableArray *) before andInlist: (NSMutableArray *) inlist andAll: (int)all andWant:(int)want {
    NSMutableArray *temp= [[NSMutableArray alloc] init];
    if(want == 0) {
        [self addList:before];
    } else if(all == want) {
        [self addList:before andAfter:inlist];
        
    }
    else
    {
        NSMutableArray *newarr= [NSMutableArray arrayWithArray:before];
        temp= [NSMutableArray arrayWithArray:inlist];
        [temp removeObjectAtIndex:0];
        [newarr addObject: [inlist objectAtIndex: 0]];
        [self calc:newarr andInlist:temp andAll:all-1 andWant:want-1];
        [self calc:before andInlist:temp andAll:all-1 andWant:want];
    }
}

-(NSMutableArray *) calc:(int)all andWant:(int)want {
    list =[[NSMutableArray alloc]init];
    NSMutableArray *alllist = [[NSMutableArray alloc] init];
    NSMutableArray *empty = [[NSMutableArray alloc] init];
    for(int i=1; i<=all; i++) {
        [alllist addObject: [NSString stringWithFormat:@"%d", i]];
    }
    [self calc:empty andInlist:alllist andAll:all andWant:want];
    return list;
}
@end

int main(int argc, const char * argv[])
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    Combinations *cb = [Combinations alloc];
    int all=4;
    int want=2;
    if(argc == 3)
    {
        all = atoi(argv[1]);
        want = atoi(argv[2]);
    }
    NSMutableArray *arr=[cb calc:all andWant:want];
    printf("\n%d取%d,結果共%lu個\n", all, want, arr.count);
    for(int i=0; i<arr.count; i++) {
        NSMutableArray *temp =[arr objectAtIndex:i];
        for(int j=0; j<temp.count; j++) {
            printf("%s ",  [[temp objectAtIndex:j] UTF8String]);
        }
        puts("");
    }
    [pool drain];
    return 0;
}

沒有留言: