注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

一个TC题目的解法  

2006-12-30 22:17:51|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Given an int m and a vector <int> a containing n numbers, return the result of the following expression:  
 
Notes  
- The expression is calculated from top to bottom.  
- "x mod y" means the remainder of x divided by y.  
- Assume 0! = 1.  
Constraints  
- a will contain between 1 and 50 elements, inclusive.  
- Each element of a will be between 0 and 2147483647, inclusive.  
- m will be between 1 and 40000, inclusive.


说下这个题目的解法吧:
其实很简单的,如果有这个定理的话:

有X、Y和Z三个正整数,且X * Y大于Z,则有:
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z

根据这个定理,可以逐步把问题化解,以下是我的代码:
import java.util.*;
//import java.math.*;

public class modeSolution {
    public int modOP(int x, int y, int z) {
        if ( x * y > z)
            return (((x % z) * (y % z)) % z);
        else
            return (x * y) % z;
    }
    public int modFunc(int base, int times, int z){
        int result = 1;
        for(int i = 0; i < times; i++)
        {
            result = modOP(result, base, z);
        }
        return result;
    }
    public int solution(int m,  ArrayList<Integer> a) {
        int i = 0, j = 0;
        int result = 1;
        int last, now = 0;
        for(i = 1; i <= a.get(0); i++)
        {
            result = modOP(result, i, m);
        }
        result = result % m;
        System.out.println("1: " + result);
        for(i = 1; i < a.size(); i++)
        {
            last = result;
            for(j = 1; j <= a.get(i); j++)
            {
                now = modFunc(last, j, m);
                System.out.println(now);
                last = now;
            }
            result = now;
        }
        return now;
    }
/*    public static void main(String[] args) {
        modeSolution sample = new modeSolution();
        ArrayList<Integer> a = new ArrayList<Integer>();
        a.add(3);
        a.add(4);
//        a.add(5);
//        a.add(1);
//        a.add(0);
        int m = 5;
        int result = sample.solution(m, a);
        System.out.print("The result is : ");
        System.out.println(result);
       // long ss = (long)Math.pow(2,120) % 5 ;
       // System.out.println("The test result: " + ss);
    }
 */
}

注释掉的部分是属于测试部分!
根据这次编程经历:我个人认为,写程序的时候,算法步骤一定要清楚,并且最好写下来,用循环不定式推导以下,这样的话,程序正确性和高效性就很容易保证了!

  评论这张
 
阅读(167)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017